找到偶数次出现的数字

Question

给定一个数组,其中每个数字的出现次数是奇数,除了一个出现次数是偶数的数字.找到偶数出现的数字.

例如

1, 1, 2, 3, 1, 2, 5, 3, 3

输出应该是:

2

以下是限制:

1. 数字不在范围内.
2. 就地做.
3. 所需的时间复杂度为O(N).
4. 数组可能包含负数.
5. 数组未排序.

由于上述限制,我的所有想法都失败了:基于比较的排序,计数排序,BST,散列,暴力.

我很想知道:XORing会在这里工作吗？如果有,怎么样？

Answer 1

请参阅以下文章：运行时间为 O(n) 且还进行就地排序的排序算法，假设最大位数不变，我们可以在 O(n) 时间内对数组进行就地排序。

接下来就是统计每个数字出现的次数，平均需要 n/2 时间才能找到出现次数为偶数的一个数字。