javascript - 高效的重复搜索算法

Question

我需要一个脚本来有效地搜索一维数组中的所有重复项。我尝试了一种天真的方法:

for(var i=0, ii<arr.length-1; i<ii; i++)
    for(var j=i+1, jj<arr.length; j<jj; j++)
        if(arr[i] == arr[j])
            // remove the duplicate

非常简单，但如果数组包含大量值，则需要很长时间。我使用的表通常包含数十万个值，因此此操作所需的迭代次数非常巨大!

如果有人有想法!？

Answer 1

使用 LinkedHashSet 或 OrderedHashSet 实现，它不允许重复，并在插入、查找和删除时提供预期的 O(1)。由于您的 OP 说您要删除重复项，因此没有比 O(n) 更快的方法来执行此操作。在包含 1,000,000 个项目的数组中，最长时间为 16 毫秒

• 创建一个LinkedHashSet hs
• foreach 对象 obj in arr-- hs.add(obj);

具有良好散列函数的复杂性预计为 O(n)。