给定一个整数数组。数组中每个数字出现的次数都是奇数,但只有1个数字出现了偶数次。请找到那个数字。
以下是我在stackoverflow上看到的不起作用的解决方案。我无法找到该解决方案的链接,我想知道除非我做错了什么,否则是否有人能帮助我理解为什么此解决方案不正确。
我们首先对数组中的所有元素进行异或运算。让我们称其为
以下是我在stackoverflow上看到的不起作用的解决方案。我无法找到该解决方案的链接,我想知道除非我做错了什么,否则是否有人能帮助我理解为什么此解决方案不正确。
我们首先对数组中的所有元素进行异或运算。让我们称其为
aWithOutDuplicate
,其中包含除重复元素外的所有奇数元素。然后我们对所有元素进行OR运算。让我们称其为aAllUnique
,它应该包含所有唯一的元素。aWithOutDuplicate
和aAllUnique
进行异或运算应该得到重复的元素。 int arr[] = {1,2,3,4,5,6,7,8,4,9};
int aWithOutDuplicate = 0;
int aAllUnique = 0;
for(int i=0;i<arr.length;i++) {
aWithOutDuplicate ^= arr[i];
aAllUnique |= arr[i];
}
cout << (aWithOutDuplicate ^ aAllUnique);
更新: 我想知道这个问题能否在O(n)时间和O(1)空间复杂度下解决。