在一百万个元素的数组中查找唯一的唯一元素 [英] Find the only unique element in an array of a million elements

问题描述

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

I was asked this question in a recent interview.

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

You are given an array that has a million elements. All the elements are duplicates except one. My task is to find the unique element.

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

我的方法是在for循环中遍历整个数组，然后创建一个map，其索引为数组中的number，而value为出现的数字的frequency在数组中.然后再次遍历我们的地图，并返回值为1的索引.

My approach was to go through the entire array in a for loop, and then create a map with index as the number in the array and the value as the frequency of the number occurring in the array. Then loop through our map again and return the index that has value of 1.

我说我的方法将花费O(n)的时间复杂性.面试官告诉我以小于O(n)的复杂度对其进行优化.我说过，我们不能，因为我们必须遍历具有一百万个元素的整个数组.

I said my approach would take O(n) time complexity. The interviewer told me to optimize it in less than O(n) complexity. I said that we cannot, as we have to go through the entire array with a million elements.

最后，他似乎并不满意，然后转到下一个问题.

Finally, he didn't seem satisfied and moved onto the next question.

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

I understand going through million elements in the array is expensive, but how could we find a unique element without doing a linear scan of the entire array?

PS:数组未排序.

推荐答案

我敢肯定，如果不遍历整个数组就无法解决此问题，至少在没有其他信息的情况下(例如元素被排序并限制为某些值)，因此该问题的最小时间复杂度为O(n).但是，如果每个元素在数组中的偶数次，则可以使用基于XOR的解决方案将内存复杂度降低到O(1)，这可能是该问题的最常见变体，如果有兴趣的话给你:

I'm certain that you can't solve this problem without going through the whole array, at least if you don't have any additional information (like the elements being sorted and restricted to certain values), so the problem has a minimum time complexity of O(n). You can, however, reduce the memory complexity to O(1) with a XOR-based solution, if every element is in the array an even number of times, which seems to be the most common variant of the problem, if that's of any interest to you:

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

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

Basically, every XORed element cancels out with the other one, so your result is the only element that didn't cancel out.

这篇关于在一百万个元素的数组中查找唯一的唯一元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！