高效的重複搜索算法

我需要一個腳本來有效地搜索一維數組中的所有重複項。我嘗試了天真的方法：高效的重複搜索算法

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

很簡單，但它需要太長的時間，如果陣列中含有大量組值。我使用的表格通常包含數十萬個值，因此此操作所需的迭代次數是巨大的！

如果有人有想法！

來源

2014-02-14 guy777

可能重複http://stackoverflow.com/questions/840781/easiest-way-to-find-duplicate-values-in-a-javascript-array – Merlin

，除非你對我的值會有些限制投票支持dup。 –

使用LinkedHashSet或OrderedHashSet實現，它不允許重複並在插入，查找和刪除時提供預期的O（1）。由於你的OP說你想刪除重複項，所以沒有比O（n）更快的方法來做到這一點。在1,000,000項的數組最大時間爲16ms的

創建LinkedHashSet HS
的foreach對象物obj中ARR - hs.add（OBJ）;

複雜性預計O（n）具有良好的散列函數。

來源

2014-02-14 11:51:03 TheJackal

嚴格來說，散列集並不能保證'O（n）'的複雜性。 – AlexD

我從來沒有說過它，我說從數據集中刪除重複是最壞的情況O（n）。 HashSet保證操作的O（1） – TheJackal

我的意思是使用散列集並不能保證總體的'O（n）'複雜性。不，哈希集合由於可能的哈希衝突而不會_guarantee_ O（1）。 – AlexD

This代碼可能是最有效的方式，你可以做到這一點..！這不過是直接執行set。

function eliminateDuplicates(arr) { 
    var i, 
     len=arr.length, 
     out=[], 
     obj={}; 

    for (i=0;i<len;i++) { 
    obj[arr[i]]=0; 
    } 
    for (i in obj) { 
    out.push(i); 
    } 
    return out; 
}

來源

2014-02-14 11:57:18 MissingNumber

高效的重複搜索算法

回答

相關問題