其中只发生一次阵列中数 | 其中只发生一次阵列中数

本文介绍了其中只发生一次阵列中数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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

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

示例

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

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