从阵列中获取数字的高效算法

Question

这是问题所在:

在一个数组中有2*N + 1个整数,并且有N对int数,i,e,两个1或两个3等,因此只有一个int数,它没有对.

问题是如何用高效算法找到这个数字.

感谢您提供任何线索或评论.

Answer 1

好的,好的,这是我的评论的解释.: - /

missingNum = 0
for each value in list
   missingNum = missingNum ^ value //^ = xor
next
print(missingNum)

这是一个线性算法,O(n).

那么这里发生了什么？再说了,我们有[2,1,3,1,2],对于熟悉XOR运算符,知道1 ^ 1 = 0,0 ^ 0 = 0和 1 ^ 0 = 1,0 ^ 1 = 1(记得有没有进位)

所以基本上,当我们对一个位序列(100110111)进行异或,并且它具有偶数时1,每个都将XOR自身变为零...如果数量为1's奇数,则XOR产生一个1

所以在我们的例子中,从lsb开始

2 : 0010
1 : 0001
3 : 0011
1 : 0001
2 : 0010

lsb bit: 0 ^ 1 ^ 1 ^ 1 ^ 0 : 1 
2nd bit: 1 ^ 0 ^ 1 ^ 0 ^ 1 : 1 
3rd bit: 0 ^ 0 ^ 0 ^ 0 ^ 0 : 0 
4th bit: 0 ^ 0 ^ 0 ^ 0 ^ 0 : 0

所以我们缺少的号码是

0011 = 3