由网友(下①站--→幸福终点站)分享简介：可能重复： 找到一个单一的数字在列表 鉴于数字数组，除了一个号码的所有其他人，出现两次。应该用什么算法来查找只发生一次在这个数字阵列？Given an array of numbers, except for one number all the others, occurtwice. What shoul...

可能重复：   找到一个单一的数字在列表

鉴于数字数组，除了一个号码的所有其他人，出现 两次。应该用什么算法来查找只发生一次在这个数字 阵列？

Given an array of numbers, except for one number all the others, occur twice. What should be the algorithm to find that number which occurs only once in the array?

示例

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

应该返回4

should return 4

推荐答案

让只发生一次数组中的数量是 X

Let the number which occurs only once in the array be x

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

由于 A ^ A = 0 和 A ^ 0 = A

这发生在对数字抵消，结果被存储在 X

Numbers which occur in pair cancel out and the result gets stored in x

工作code在C ++

Working code in 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;
}