JavaScript で配列から重複要素を削除するための 5 つの効率的なアルゴリズム サンプル コードの詳細な紹介

しばらく面接の準備をしていたので、長い間ブログを更新していませんでしたが、基本的な知識のポイントを確認したので、面接でよくある質問をいくつか紹介します。

通常のインターネット会社に筆記試験と面接を受けに行くと、次のような JavaScript を使用した配列重複排除の実装 コーディングの問題に遭遇することになります。 、デモとソースコードを添付します。

1. 配列走査方法

重複を削除する最も簡単な方法、

実装アイデア:

新しい配列を作成し、受信配列を走査し、値が新しい配列にない場合は新しい配列に追加します;注意事項 : 値が配列内にあるかどうかを判断するメソッド「indexOf」は、IE8 より下ではサポートされていません。ソース コードは次のとおりです。次のように:

// 最简单数组去重法
function unique1(array){
  var n = []; //一个新的临时数组
  //遍历当前数组
  for(var i = 0; i < array.length; i++){
    //如果当前数组的第i已经保存进了临时数组，那么跳过，
    //否则把当前项push到临时数组里面
    if (n.indexOf(array[i]) == -1) n.push(array[i]);
  }
  return n;
}

// 判断浏览器是否支持indexOf ，indexOf 为ecmaScript5新方法 IE8以下（包括IE8， IE8只支持部分ecma5）不支持
if (!Array.prototype.indexOf){
  // 新增indexOf方法
  Array.prototype.indexOf = function(item){
    var result = -1, a_item = null;
    if (this.length == 0){
      return result;
    }
    for(var i = 0, len = this.length; i < len; i++){
      a_item = this[i];
      if (a_item === item){
        result = i;
        break;
      }  
    }
    return result;
  }
}

2. オブジェクトのキーと値のペアリング メソッド

このメソッドは他のメソッドよりも高速ですが、より多くのメモリを消費します。

新しい js オブジェクトと新しい配列を作成します。 、そして、受信配列を走査するときに、

値がjsオブジェクトのキーであるかどうかを判断し、そうでない場合は、それをオブジェクトに渡します。キーを追加して、新しい配列に入れます。 注意: それが JS オブジェクト キーであるかどうかを判断するとき、「toString()」は受信キーに対して自動的に実行されます。たとえば、a[1]、a["1" などです。 ]。上記の問題を解決するには、やはり「indexOf」を呼び出す必要があります。

// 速度最快， 占空间最多（空间换时间）
function unique2(array){
  var n = {}, r = [], len = array.length, val, type;
    for (var i = 0; i < array.length; i++) {
        val = array[i];
        type = typeof val;
        if (!n[val]) {
            n[val] = [type];
            r.push(val);
        } else if (n[val].indexOf(type) < 0) {
            n[val].push(type);
            r.push(val);
        }
    }
    return r;
}

3.

やはり「indexOf」を呼び出す必要があります。パフォーマンスはメソッド 1 と似ています。

実装アイデア

: 現在の配列の i 番目の項目が最初に現在の配列の i 以外の位置に出現する場合。配列の場合、i 番目の項目が重複するものは無視されることを意味します。それ以外の場合は、結果の配列を保存します。

function unique3(array){
  var n = [array[0]]; //结果数组
  //从第二项开始遍历
  for(var i = 1; i < array.length; i++) {
    //如果当前数组的第i项在当前数组中第一次出现的位置不是i，
    //那么表示第i项是重复的，忽略掉。否则存入结果数组
    if (array.indexOf(array[i]) == i) n.push(array[i]);
  }
  return n;
}

4.

ネイティブ配列の「sort」メソッドのソート結果はあまり信頼できませんが、この欠点は順序を考慮しない重複排除には影響しません。

実装アイデア:

受信した配列をソートします。ソート後、同じ値が隣接し、トラバースするときに、前の値と重複しない値のみを新しい配列に追加します。

// 将相同的值相邻，然后遍历去除重复值
function unique4(array){
  array.sort(); 
  var re=[array[0]];
  for(var i = 1; i < array.length; i++){
    if( array[i] !== re[re.length-1])
    {
      re.push(array[i]);
    }
  }
  return re;
}

5. 最適化された配列トラバーサルメソッド

は、海外のブログ投稿から来ています。

実装アイデア

: 重複することなく右端の値を取得し、それを新しい配列に入れます。 (重複値が検出された場合、現在のループを終了し、次の先頭ループの判定に移ります)

// 思路：获取没重复的最右一值放入新数组
function unique5(array){
  var r = [];
  for(var i = 0, l = array.length; i < l; i++) {
    for(var j = i + 1; j < l; j++)
      if (array[i] === array[j]) j = ++i;
    r.push(array[i]);
  }
  return r;

以上がJavaScript で配列から重複要素を削除するための 5 つの効率的なアルゴリズム サンプル コードの詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。