java - 在一百万个元素的数组中找到唯一的唯一元素

Question

我在最近的一次采访中被问到这个问题。

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

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

我的方法是在 for 循环中遍历整个数组，然后创建一个 map，索引为 number数组和值作为数组中数字出现的频率。然后再次遍历我们的 map 并返回值为 1 的索引。

我说过我的方法需要 O(n) 时间复杂度。面试官告诉我优化它的复杂度小于O(n)。我说我们不能，因为我们必须遍历具有一百万个元素的整个数组。

最后，他似乎并不满意，继续下一个问题。

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

PS:数组没有排序

Answer 1

我敢肯定，如果不遍历整个数组就无法解决这个问题，至少如果你没有任何附加信息(比如对元素进行排序并限制为某些值)，那么问题就来了O(n) 的最小时间复杂度。但是，如果每个元素在数组中出现偶数次，则可以使用基于 XOR 的解决方案将内存复杂度降低到 O(1)，这似乎是最常见的变体问题，如果您对此感兴趣的话:

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

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