考虑这个问题:
You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer.
解决方法:
出现次数为奇数的整数将有 0 对或多对和一个单数。所以，如果我们能找到摆脱所有对的方法，那么我们剩下的就是单个数字。现在，什么摆脱了对？提示:想想一个运算符。
XOR 可以解决问题。它为您提供了没有额外内存的 O(n) 解决方案。
int GetSpecialOne(int[] array, int length)
{
int specialOne = array[0];
for (int i=1; i < length; i++)
{
specialOne ^= array[i];
}
return specialOne;
}
我不明白如何通过累加每个元素的 XOR 来减少数组产生特殊整数。它是如何工作的？
最佳答案
之所以有效，是因为 (N xor Q) xor Q = N。
恰好一个整数出现奇数次，因此它将是唯一没有从列表中“消失”的数字。所有其他数字出现的次数都是偶数，所以它们都以 2 为一组出现(可以想象)，所以它们都“消失”了。此外，XOR 之间的“距离”无关紧要:(((N xor Z) xor Q) xor Z) xor Q = N。即使在对之间存在中间 XOR，Z 和 Q 也会“抵消” .
关于c - 如何使用 XOR 查找数组中出现次数为奇数的单个元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4985970/