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

Question

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

但我不明白，当面试官强行说出“一个非常大的数组，比如说给定数组中有1000万个元素”。在

我需要改变方法吗？如果没有，那么实现这一目标的效率应该是什么？在

注：Algo或实现是语言不可知的。在

谢谢。在

Answer 1

要记住的一点是，O-符号并不一定告诉你什么算法最快。如果一个算法是O（n logn），而另一个算法是O（n²），则存在一些值M，因此第一个算法对于所有n>；M都更快。但是M可能比您需要处理的数据量大得多。在

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

无论如何，我倾向于不使用排序，因为如果您只需要查找重复项，那么排序所做的工作将超过您的需要。你不应该仅仅为了找到重复的元素，而需要把元素排列整齐。这对我来说意味着一种可能不是最好的答案。在

（*）注意，在Java8中，每个bucket中的元素将位于某种搜索树中，可能是红黑树，而不是线性列表中。所以算法仍然是O（nlogn），而且可能仍然比排序快得多。在

Answer 2

面试官希望你回答一些关键问题，比如：如果你不能在内存中加载数组，那么how much I can load。解决问题的步骤如下：

1. 您需要将数组除以可用内存量。在
2. 假设你一次可以加载1M号码。您已经在k parts中拆分了数据。加载第一个1M并构建它的Min Heap。然后移除顶部并对Min Heap应用Heapify。在
3. 对数据的其他部分重复相同的操作。在
4. 现在您将有K个排序的拆分。在
5. 现在从每个K拆分中获取第一个数字，然后再次构建一个Min Heap。在
6. 现在从Min Heap中删除顶部，并将值存储在temporary variable中，以便与下一个数字进行比较，以找到重复项。在
7. 现在从上次删除编号的同一拆分（部件）中获取下一个编号。将该数字放在Min Heap的顶部并应用Heapify。在
8. 现在，Min Heap的顶部是下一个排序的数字，并将其与temporary variable for finding the duplicates. Update the临时变量“if number不重复”进行比较。在

Answer 3

你可以用O（nlog（n））：

• 对数组排序
• 在一个过程中找到重复项（它们将彼此相邻）。在

我想这就是面试官想听的。在

如果您进行了合并排序或快速排序，则可以在合并时在隐藏时间内找到重复项。 这些可以“就地”实现，如果数组太大而无法装入内存，则可以“部分”实现。在