小编典典

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

algorithm

给定一个数字数组,除了一个数字外,其他所有数字都出现两次。查找仅在数组中出现一次的数字的算法应该是什么?

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

应该返回4


阅读 213

收藏
2020-07-28

共1个答案

小编典典

令在数组中仅出现一次的数字为 x

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

由于a ^ a = 0a ^ 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;
}
2020-07-28