找到一百万个元素中唯一的唯一元素

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元素都会与另一个元素取消,因此您的结果是唯一没有取消的元素.