在一百万个元素的数组中查找唯一的唯一元素

Question

在最近的一次采访中有人问我这个问题。

您将获得一个包含一百万个元素的数组。除了一个元素外，所有元素都是重复的。我的任务是找到独特的元素。

var arr = [3, 4, 3, 2, 2, 6, 7, 2, 3........]

我的做法是要经过在整个数组for循环，然后创建一个map索引作为number数组中和value的frequency数组中出现的次数。然后再次遍历我们的地图，并返回值为1的索引。

我说我的方法会花费O(n)时间。面试官告诉我要以低于O(n)复杂度的方式对其进行优化。我说过，我们不能，因为我们必须遍历具有一百万个元素的整个阵列。

最后，他似乎并不满意，转而关注下一个问题。

我知道遍历数组中的数百万个元素非常昂贵，但是如何在不对整个数组进行线性扫描的情况下找到唯一的元素呢？

PS：数组未排序。

Answer 1

我敢肯定，如果不遍历整个数组就无法解决此问题，至少在没有任何其他信息（例如元素被排序并限制为某些值）的情况下，因此问题的发生时间最短复杂性O(n)。但是，O(1)如果每个元素在数组中的偶数次，则可以将内存复杂度降低到基于XOR的解决方案，如果您感兴趣，这似乎是问题的最常见变体：

int unique(int[] array)
{
    int unpaired = array[0];
    for(int i = 1; i < array.length; i++)
        unpaired = unpaired ^ array[i];
    return unpaired;
}

基本上，每个XORed元素都会与另一个元素抵消，因此您的结果是唯一没有抵消的元素。