在一个数组中找出出现偶数次的整数，而其他整数出现奇数次数。与之相关的是IT技术问题。

Question

给定一个整数数组。数组中每个数字出现的次数都是奇数，但只有1个数字出现了偶数次。请找到那个数字。

以下是我在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)空间复杂度下解决。

- Kay

---

你错了。{1,2,3,5,6,7,8,9} 没有 重复。{4} 重复了一次。其中一个是奇数。或者你的意思是：“查找出现偶数次的数字”吗？ - wildplasser

我之所以选择这个例子是为了简单起见。当我说“重复”时，我的意思是该数字出现的次数。有了这个定义，只有4次出现偶数次（2次），其余都是奇数次（在这个例子中是1次）。 - Kay

我认为wildplasser所说的是，重复一个数字会使所有出现在集合中的数字都排在一起。然而，我不认为“重复”这个词的定义需要这样做。 - Lasse V. Karlsen

Answer 1

这个O(n), O(1)空间解决方案只有在数组元素处于范围[1,n-1]时才适用，其中n为数组大小。 [在下文提到的一些调整中，将适用于[0,n-1]。]

• Scan the array and do the following

  for(i=0; i < n; i++) 
    A[A[i]]=A[A[i]]*(-1)
  

• All array elements with odd occurrences will have a negative value at the end of the scan. The element with the even number of occurrence will have a positive value.

一些小调整： 如果数组范围是从[0，n-1]，您可以在第一次传递期间使用特殊字符替换'0'（而不是取反）的特殊情况。您必须在第二遍传递期间将特殊字符恢复为'0'等。

- Bugaboo

---

[1，n-1]的限制很烦人。但这真的很聪明，我找不到任何错误。+1。 - gsgx

为什么这是一个常数空间？因为需要将输入数组存储在内存中才能使其工作。 - Artem Tikhomirov

Answer 2

这种方法行不通，因为无法区分出现偶数次的数字和根本没有出现过的数字。考虑这个4位的例子：

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

现在，将任何数字（<= 15，因为它是4位）添加到列表中两次。或运算符将保持不变，因为所有位都已开启，对于x的所有4位值，0xf | x == 0xf。异或运算符将保持不变，因为对于x的所有值，0xf ^ x ^ x == 0xf。因此，您的方法的反例可能是，例如{5, 10, 1, 1}。

- Kevin

Answer 3

假设你有数组：a，b，a，b，a，c 那么输出应该是b。 我会尝试解释为什么你的算法是错误的。当你应用OR操作时，你假设你将得到唯一的数字。是的，当然，a | a | a == a，但是通过执行以下操作，你将得到什么值：a | b | c ==？（取决于a，b，c，可能所有位都将设置为1） 这与执行XOR不同。

- numa

Answer 4

在下面的代码中，我使用暴力方法找到了重复偶数次的数字，而没有使用标准库函数map：

//! Print integers occurring an even number of times in array a.

#include <iostream>

int main() {
    int arr[] = { 9, 12, 23, 10, 12, 12, 15, 23, 14, 12, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int b[n], count = 0, c[100];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            if (arr[j] == arr[i])
                b[i] = ++count;
        count = 0;
    }
    for (int i = 0; i < n; i++)
        c[arr[i]] = 0;
    for (int i = 0; i < n; i++) {
        if (c[arr[i]] == 1)
            continue;
        if (b[i] % 2 == 0)
            std::cout << arr[i] << std::endl;
        c[arr[i]]++;
    }
    return 0;
}

- Swapnil Rahalkar

---

这种方法的描述看起来很到位。(如果它包含了所有非显而易见的内容的注释，缩进更加传统：像main()这样的“全局事物”在左边缘，每个级别8（或4）个空格，并且节省垂直空间：不需要大括号的地方没有大括号，开放大括号不在自己的一行中，那么我会更喜欢这个演示文稿。) 不要习惯性地使用命名空间std;。 - greybeard

谢谢您的评论。能否请您指导我如何在Stack Overflow上编写适当的答案？因为我现在是一个初学者... - Swapnil Rahalkar

你根本不知道自己在问什么；其中一部分有准备好的答案：如何提出一个好问题？。还有更详细的 - 让我插入一个 问题清单。经验法则：你的帖子将被阅读_很多_次 - 写作时应该认真（例如，使用拼写检查器，在适当的情况下使用大写字母，标点符号后面加空格）。当评论要求提供额外信息或澄清时，请编辑您的帖子而不是重新发表评论。 - greybeard

感谢您的编辑...我在Stack Overflow上学到了如何编写代码的想法...在以后回答问题时，我会遵循您的建议...再次感谢。 - Swapnil Rahalkar

刚刚检查发现一个错误：“在数组a中”应该是“在数组arr中”（或者是“在数组<code>arr</code>中”）。太糟糕了，我的IDE甚至没有警告我，即使它处理重命名时的注释。更糟糕的是，我没有尽到应有的注意义务…… - greybeard