在一个非常大的数组中查找重复项的算法

Question

在一次技术面试中，我被问到了这个问题。我知道用（在Java中）HashSet的方法来解决这个问题。

但是当面试官强调“给定数组中有非常大的数组，比如1000万个元素”这个词时，我不明白该怎么办。

我需要改变方法吗？如果不需要，如何高效地解决问题？

附注：算法或实现与语言无关。

谢谢。

- Sam

---

你需要在发现重复项时将其删除，还是需要将其打印出来？ - Joe T. Boka

他所说的“一个非常大的数组，比如给定数组中有1000万个元素”，意思是你不能将它们全部存储在内存中。数组的大小更大，而内存的大小更小。 - YoungHobbit

在Python中，您可以使用collections.Counter而无需算法：from collections import Counter; c = Counter(<array>)所有计数大于1的都是重复项。 - AChampion

@Abhishek 谢谢您的解释。您能告诉我们如何处理这个问题吗？我的意思是应该使用什么样的数据结构和/或算法？ - Sam

面试官想要了解你的解决问题的能力，看看你是否知道自己在说什么。他们可能正在寻找一种基于磁盘的解决方案。向面试官询问一些有关问题的问题即可。 - Chris

Answer 1

面试官期望你回答以下问题，例如：如果你无法在内存中加载数组，则可以加载多少数据。以下是解决此问题的步骤：

1. 将数组分成可用内存大小的部分。
2. 假设您每次可以加载1M个数字。您将数据分成k个部分。您加载前1M个数字并构建其最小堆。然后删除顶部并在最小堆上应用Heapify。
3. 对于数据的其他部分，请重复相同的操作。
4. 现在您将拥有K个已排序的部分。
5. 现在从每个K部分中获取第一个数字，并再次构建最小堆。
6. 现在从最小堆中删除顶部，并将该值存储在临时变量中，以便与下一个出现的数字进行比较以查找重复项。
7. 现在从上次删除数字的相同部分（部分）获取下一个数字。将该数字放在最小堆的顶部并应用Heapify。
8. 现在，最小堆的顶部是您下一个已排序的数字，并将其与临时变量进行比较以查找重复项。如果数字不是重复项，请更新临时变量。

- YoungHobbit

---

是的，无论面试官寻求什么，我能装多少？这个问题都只会被看作是积极的。 - riddle_me_this

Answer 2

你可以在O(nlog(n))的时间复杂度内完成：

• 对数组进行排序
• 在一次遍历中找到重复项（它们将紧挨在一起）。

我认为这就是面试官想听到的答案。

如果你使用归并排序或快速排序，查找重复项可以在合并时以隐藏时间完成。 如果数组太大无法放入内存，则可以“原地”或“分段”实现这些操作。

- Reblochon Masque

---

数据的大小超过了可用的内存。归并排序再次需要相同大小的额外内存，因此归并排序不是答案。 - YoungHobbit

假设对象是可排序的，而不仅仅是定义相等。如果对象是可哈希的，则可以通过创建哈希映射或字典在1次遍历中完成此操作。 - AChampion

我们不知道这个，Abhishek，你在这里推测。是的，achampion，但这就是面试中op提出的，而那似乎并没有让面试官满意。 - Reblochon Masque

Answer 3

需要翻译的内容如下：

需要记住的一件事是，O表示法并不一定告诉你哪个算法是最快的。如果一个算法是O（n log n），另一个算法是O（n²），那么存在某个值M，使得第一个算法对于所有n > M都更快。但是，M可能比您需要处理的数据量要大得多。

我提出这个问题的原因是我认为HashSet可能仍然是最好的答案，尽管我必须对其进行分析才能确定。假设您不允许设置具有1000万个桶的哈希表，您仍然可以设置一个合理大小的表。例如，您可以创建一个大小为100,000的HashSet。然后，桶将成为对象集。如果n是数组的大小，则平均桶大小将为n / 100000。因此，要查看元素是否已经在HashSet中，并且如果没有，则需要添加它，将需要计算哈希值的固定时间，并且搜索存储在线性列表中的桶中的元素将需要O（n）的时间。从技术上讲，这意味着找到所有重复项的算法是O（n ² ）。但是，由于n ² 中的一个n是表示线性列表的，该列表比数组大小小得多（100000倍），因此我认为它仍然需要比O（n log n）排序快得多，对于1000万个项目。M的值，即O（n log n）排序变得更快的点，可能要大得多。（我只是猜测；要确定需要一些分析。）

我倾向于不使用排序，因为如果您所需做的只是查找重复项，则排序比您需要的工作要多。您不需要将元素按顺序排列，只需查找重复项即可。这对我来说表明排序可能不是最好的答案。

（*）请注意，在Java 8中，每个桶中的元素将是某种搜索树，可能是红黑树，而不是线性列表。因此，算法仍将是O（n log n），并且仍然可能比排序快得多。

- ajb

Answer 4

简而言之，您需要从数组中找出所有唯一的元素。

因此，您可以创建一个对象，并将数组中的每个元素作为对象的属性添加。

function uniqueArray(arr){
    var length = arr. length,
        uniqueElementArray = [];
    while(length >= 0){
        obj [arr[length]] = true;
        length-- ;

    }

    for(var i in obj){
       uniqueElementArray.push[i];
    }
    return uniqueElementArray;
}

- Govind Kalyankar

Answer 5

假设非常大的数组可以适应内存，但留下很少的附加内存（即类似于数组大小的另一个数据结构）来处理，则在一些假设条件下，您可以在O（n）时间内进行就地操作，而不需要额外的内存。
假设1：数组中的所有值：0 <= 值 <数组长度（10,000,000）
假设2：您可以修改数组。

>>> arr = [3, 1, 3, 5, 4, 3, 4, 2, 1]
>>> for i, v in enumerate(arr):
>>>     while arr[v] != arr[i]:
>>>         arr[i], arr[v] = arr[v], arr[i]
>>>         v = arr[i]
>>> arr
[3, 1, 2, 3, 4, 5, 4, 3, 1]

重复项出现在值不等于索引的位置。

>>> [v for i, v in enumerate(arr) if i != v]
[3, 4, 3, 1]

- AChampion