0

重複の可能性：
JavaScript配列で重複する値を見つける最も簡単な方法

何千もの要素を持つ配列があり、

同じ値の要素が2つ以上return trueある場合に必要です。

for loopを実行し、要素のすべてのペアをチェックして答えを見つけることができることを私は知っています。

しかし、もっと速い方法はありますか？そして、最良の方法は何ですか？

4

7 に答える 7

1

それを並べ替えて（コンパレータが何であれ）、スキャンします。O(n log(n))。

于 2012-06-05T14:25:14.087 に答える
1

これは基本的に要素識別問題です。あなたはそれについて読むことができますが、1000 個の要素しかないため、最適化はおそらく価値がありません.

本当に最適化したい場合は、要素をハッシュ テーブルにプッシュし、衝突が重複しているかどうかを確認できます。これにより、平均（償却）でO（n）が得られますが、最悪の場合はO（n ^ 2）になります。

于 2012-06-05T14:26:27.443 に答える
0

Arrayの組み込み操作はあなたにとって見事に機能すると思いindexOfます（ソートする必要のあるデータによって異なります）

// Filter out all instances that occur twice or more.

var example = [ 1, 2, 3, 3, 3, 5, 4, 3, 5, 3 ];
var result = Array.filter( function ( element ) {
    return this.indexOf( element ) >= 2;
}  
// result is an array of [3,5]

return result.length === 0;
于 2012-06-05T14:33:10.950 に答える
0

配列をトラバースして、配列で見つかった要素（文字列に変換されたもの）と等しいオブジェクトキーを設定できます。キーがすでに存在する場合は、値が重複している2つの要素が配列に見つかりました

function isAllDistinct() {
    var elements  = { },
        yourarray = [...];

    for (i=0, l=yourarray.length; i < l; i++) {
       var key = yourarray[i] + '';  // alternative to yourarray[i].toString()
       if (!elements[key]) {
         elements[key] = 1;
       }
       else {
         return false;
       }
    }
    return true;
}

複雑さ：O（n）

于 2012-06-05T14:33:48.870 に答える
0

これを試して：

Array.prototype.elementsNotDistinct = function () {
    var i, j, length = this.length - 1;

    for(i = 0; i < length; i++)
        for (j = i + 1; j <= length; j++)
            if (this[i] === this[j]) return true;

    return false;
};

次に、a必要なすべての配列がある場合は、次のようにします。

if (a.elementsNotDistinct()) {
    // do something
}
于 2012-06-05T14:31:53.933 に答える
0

おそらく最速の方法は、ネイティブ メソッドを使用することです。inArrayそれらの1つではありません。indexOfそのメソッドが存在しない場合 (古いブラウザー) は、for ループを使用してデフォルトにすることができます。

于 2012-06-05T14:26:34.043 に答える
0

もっと速い方法があります。具体的な実装は、配列に何があるかによって異なります。しかし、アイデアは以下の擬似コードです。

id(element)要素の文字列識別子を返す関数があるとします。

var map = {};

for(var i = 0; i < myArray.length; i++) {
    var currentId = id(myArray[i]);
    if(map.hasOwnProperty(id)) return true;
    map[id] = true;
}

ここでの複雑さは線形です。

自然な ID がない場合は、オブジェクトを識別するプロパティから ID を作成するか、もっとスマートなことを行うことができます...ここでできる最もスマートなことは、ハッシュマップを再実装することです。

于 2012-06-05T14:27:27.990 に答える