在数组中只出现一次的数字

Question

可能重复:
在列表中查找单个数字

给定一组数字,除了一个数字,所有其他数字,出现两次.什么算法应该找到在数组中只出现一次的那个数字？

例

a[1..n] = [1,2,3,4,3,1,2] 

应该返回4

Answer 1

设数组中只出现一次的数字 x

x <- a[1]
for i <- 2 to n
   x <- x ^ a[i]
return x

从a ^ a = 0和a ^ 0 = a

成对出现的数字取消,结果存储在中 x

使用C++编写代码

#include <iostream>

template<typename T, size_t N>
size_t size(T(&a)[N])
{
    return N;
}
int main()
{
   int a [] = {1,2,3,4,3,1,2};
   int x = a[0];
   for (size_t i = 1; i< size(a) ; ++i)
   {
      x = x ^ a[i];
   }
   std::cout << x;
} 

Answer 2

1. 创建新的 int i = 0
2. XOR 每个项目都有 i
3. 在所有迭代之后,将有预期的数字 i