给定一个数字数组,除了一个数字外,其他所有数字都出现两次。查找仅在数组中出现一次的数字的算法应该是什么?
例
a[1..n] = [1,2,3,4,3,1,2]
应该返回4
令在数组中仅出现一次的数字为 x
x
x <- a[1] for i <- 2 to n x <- x ^ a[i] return x
由于a ^ a = 0和a ^ 0 = a
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; }