题目1

1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其他均指出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计这个算法实现？

解题思路：

  1. A^A=0;  A^0=A;一个数与自己进行异或结果为0，一个数与0进行异或结果为这个数本身

所以可以用异或来排除相同的数
(1^2^3^k……^1000^k)^(1^2^3^4^..^k^…^1000)=k、

代码实现（为了方便，就只考虑1-10）：

  1. import random
  2. alist = random.sample(range(1,11),10) #random.sample()生成不相同的随机数
  3. blist=alist
  4. print(alist)
  5. print
  7. # i为插入的随机位置 random.randrange()生成range范围内的随机数
  8. i=random.randrange(0,10)  
  10. # j为插入的随机数
  11. j=random.randrange(1,10)
  12. alist.insert(i,j)
  13. print(alist)
  15. s=alist[0]
  17. for x in range(1,len(alist)):
  18.    s=s^alist[x] 
  20. for y in range(0,11):
  21.     s=s^y
  23. print(s) 
  25. #第二种方法，但是开辟了辅助空间clist[]
  26. clist=[]
  27. for i in range(10):
  28.     clist.append(0)
  29. print(clist)
  31. for m in range(0,len(alist)):
  33.     clist[alist[m]-1]+=1
  34.     print(alist[m],clist[alist[m]-1])
  36. for k in range(0,len(clist)):
  37.     if clist[k]==2:
  38.         print(k+1)
  39.         break

题目2

一个数组里除了某一个数字之外，其他的数字都出现了两次。请写出程序找出这个只出现一次的数字
解题思路：
将数组里的数都异或，得到的结果就是只出现一次的那个数