デデューピングアルゴリズムの時間複雑度

Question

ここでは、配列から複製を削除する関数です。

function dedupe(arr) { 
 
    var seen = {}; 
 
    arr.forEach((e,i)=>{ 
 
     if (seen[e]) { 
 
      arr.splice(i, 1); 
 
     } 
 
     seen[e] = true; 
 
    }); 
 
    return arr; 
 
} 
 

 
console.log(dedupe([1, 2, 1, 3, 4]));

私は、この関数の時間複雑に興味があります。

Arrayが実際の配列に裏打ちされていると仮定すると、時間の複雑さは次のように分析できますか？

• seenの割り当て：O（1）
• 列挙すべての要素：重複のO（N）
• 除去：O（N）（項目によってために再割り当て必須アイテム？）
• return O（1）

これはO（n^2）アルゴリズムですか？

編集：インデックスの問題のために修正さ

。上記のパフォーマンスによって動揺したものについては

function dedupe(arr) { 
 
    var seen = {}; 
 
    for(let i = 0; i < arr.length; i++) { 
 
     const e = arr[i]; 
 
     if (seen[e]) {    
 
      arr.splice(i, 1); 
 
      i--; // we have modified the array and need to continue from the current index 
 
     } 
 
     seen[e] = true; 
 
    } 
 
    return arr; 
 
} 
 

 
console.log(dedupe([1, 2, 1, 3, 1, 4, 4, 7, 6, 7, 7, 7, 1, 5]));

、これはO（N）であると思います。

私はインプレイスからデュプリケートしたいと思っていました。 Setを使用すると、ホスト環境全体で順序が維持されます。

function dedupe(arr) { 
 
    var seen = new Set(); 
 
    for(let i = 0; i < arr.length; i++) { 
 
     seen.add(arr[i]); 
 
    } 
 
    arr.length = 0; // empty the array 
 
    return arr.concat(...seen.keys()); 
 
} 
 

 
console.log(dedupe([1, 2, 1, 3, 1, 4, 4, 7, 6, 7, 7, 7, 1, 5]));

Answer 1

一つのアプローチでは、JavaScript Setを使用することです。

const removeDuplicates = array => (new Set(array)).values() 

これはイテレータであり、配列ではありませんが、これは簡単に修正できます。また、ほとんどのブラウザではまだではなく、がサポートされています。この複雑さはO（n）でなければなりません。

あなたに類似の他のアプローチ（設定するには、おそらく同じ、私はつもりだので、それは同じ基本構造を使用して実装だと思うが）、このようになります：

const removeDuplicates = array => 
    Object.keys(array.reduce((agg, x) => { agg[x] = true; return agg }, {})) 

この時の複雑さがすべきO（m + n）とする。ここでmはユニークなアイテムの数であり、常に< = n、したがってO（n）となる。

また、作業した時間の複雑さは正しいようです。

Answer 2

あなたは、インデックスによってフィルタリングすることによりseenを救うことができる：

var t1 = [1, 2, 1, 1, 3, 1, 1, 4]; 
 
function uniqueList(list) { 
 
    return list.filter(function (value, index, arr) { 
 
     return list.indexOf(value) == index; 
 
    }); 
 
} 
 
console.log(t1); 
 
console.log(uniqueList(t1));

Answer 3

私の答えは、新しい配列を作成します。たぶんO（n）です。

function dedupe(arr) { 
 
    var result = []; 
 
    var seen = {}; 
 
    for(let i = 0; i < arr.length; i++) { 
 
     const e = arr[i]; 
 
     if (seen[e]) {    
 
      //skip 
 
     } else { 
 
      seen[e] = true; 
 
      result.push(e); 
 
     } 
 
     
 
    } 
 
    return result; 
 
} 
 

 
console.log(dedupe([1, 2, 1, 3, 1, 4, 4, 7, 6, 7, 7, 7, 1, 5]));