这段代码如何工作？

Question

您将获得一个包含正整数的数组.除了一个整数之外,所有整数都会出现偶数次.找到这个特殊的整数.

方案:

具有奇数出现次数的整数将具有0对或更多对以及一个单个数.所以,如果我们能够如何摆脱所有对,那么我们剩下的就是单个数字.什么摆脱对？提示:想想一个运营商.

异或会做到这一点.它为您提供O(n)解决方案,没有额外的内存.

int GetSpecialOne(int[] array, int length)
{
int specialOne = array[0];

for(int i=1; i < length; i++)
{
specialOne ^= array[i];
}
return specialOne;
}

Answer 1

它起作用,因为(N xor Q)xor Q = N.

恰好一个整数存在奇数次,因此它将是唯一不从列表中"消失"的数字.所有其他数字都存在偶数次,因此它们都以2的组(可以想象)出现,因此它们都"消失".此外,XOR之间的"距离"无关紧要:(((N x或Z)x或Q)xor Z)xor Q = N.即使在对之间存在中间XOR,Z'和Q'也会"抵消" .