发现偶数次重复整数数组中的其中整数其余重复次数奇数 [英] Finding EVEN number of times repeating integer in an array where rest of the integers repeat ODD number of times

问题描述

由于是整数数组。阵列中的每个号码的出现次数为奇数，但是只有1号发生的偶数次。找到这个数字。

Given is an array of integers. Each number in the array occurs an ODD number of times, but only 1 number is occurring an EVEN number of times. Find that number.

下面是我读计算器不工作的解决方案。我无法找到的链接，这种解决办法，我想知道，如果有人能帮助我理解为什么这个解决方案是不正确，除非我做错了什么下文。

Below is the solution I read on stackoverflow that does NOT work. I am unable to find the link to that solution and I was wondering if somebody could help me understand why this solution is incorrect unless I am doing something wrong below.

我们第一异或数组中的所有元素。让我们把它叫做 aWithOutDuplicate 包含除了重复者一切的奇数元素。然后，我们或全部内容。让我们把它叫做 aAllUnique 应包含所有的独特的元素。异或 aWithOutDuplicate 和 aAllUnique 应吐出重复的元素。

We first XOR all the elements in the array. Lets call it aWithOutDuplicate which contains all the odd elements except for duplicate one. We then OR all the elements. Lets call it aAllUniquethat should contain all the unique elements. XORing aWithOutDuplicate and aAllUniqueshould spit out the duplicate element.

    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）空间复杂度。

Update: I wonder if this problem can be solved in O(n) time and O(1) space complexity.

推荐答案

这方法是行不通的，因为没有办法区分一个数字出现了偶数次从一个从来没有出现在所有。考虑这4位例如：

That approach does not work because there is no way to differentiate a number that appears an even number of times from one that never appears at all. Consider this 4-bit example:

5:  1 0 1
10: 0 1 0 1
-----------
    1 1 1 1 <- both or and xor.

现在，添加任意数量（小于= 15，因为它是4位），以列表的两倍。该或是因为所有的位已经接通和 0xF的将保持不变| x == 0xF的为x的所有4位值。异或将保持不变，因为 0xF的^ X ^ X == 0xF的对所有x的值。因此，一个反例，以你的方法可能是，例如， {5，10，1，1} 。

Now, add ANY number (<= 15 since it's 4 bits) to the list twice. The or will stay the same because all the bits have been switched on and 0xf | x == 0xf for all 4-bit values of x. The xor will stay the same because 0xf ^ x ^ x == 0xf for all values of x. So a counterexample to your method could be, e.g. {5, 10, 1, 1}.

这篇关于发现偶数次重复整数数组中的其中整数其余重复次数奇数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！