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

Question

在一次技术面试中遇到了这个问题。 我知道使用(在 java 中)HashSet 来解决这个问题的方法。

但是当面试官强加“一个非常大的数组，假设给定数组中有 1000 万个元素”这个词时，我无法理解。

我需要改变方法吗？如果不是，实现这一目标的效率应该是多少？

PS:算法或实现与语言无关。

谢谢。

Answer 1

有一些关键的事情，面试官希望你像这样反问:如果你不能在内存中加载数组，那么我可以加载多少。这些是解决问题的步骤:

1. 您需要根据可用的内存量划分数组。
2. 假设您一次可以加载 100 万个号码。您已将数据拆分为 k 个部分。您加载前 1M 并构建它的 Min Heap。然后移除顶部并在 Min Heap 上应用 Heapify。
3. 对数据的其他部分重复相同的操作。
4. 现在您将有 K 个排序的拆分。
5. 现在从每个 K 拆分中获取第一个数字，并再次构建一个 Min Heap。
6. 现在从 Min Heap 中移除顶部并将该值存储在 临时变量 中，以便与下一个数字进行比较以查找重复项。
7. 现在从上次删除号码的同一拆分(部分)中获取下一个号码。将该数字放在 Min Heap 之上并应用 Heapify。
8. 现在 Min Heap 的顶部是您的下一个排序数字，并将其与 临时变量进行比较以查找重复项。如果数字不重复，则更新临时变量。