其中只发生一次阵列中数 [英] Number which occurs only once in the array

问题描述

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

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

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;
} 

这篇关于其中只发生一次阵列中数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！