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

Question

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

但是我无法理解当面试官强迫“一个非常大的数组，比如说给定数组中的1,000万元素”这个词时。

我需要改变方法吗？若否，应如何有效地做到这一点？

PS: Algo或implementation是语言不可知论。

谢谢。

Answer 1

您可以在O(nlog(N))中这样做：

• 排列数组
• 一次找到副本(它们将相邻)。

我想这正是面试官想要听到的。

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

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临时变量进行比较。

Answer 3

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

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

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;
}