2

次のようなオブジェクトを含む2つの配列があります。

[{"Start": 1, "End": 2}, {"Start": 4, "End": 9}, {"Start": 12, "End": 16}, ... ]

重複を削除しながら2つの配列をマージしたいと思います。現在、私は次のことを行っています。

array1.concat(array2);

次に、ネストされた$.eachループを実行していますが、配列がどんどん大きくなるにつれて、O(n^2)実行に時間がかかり、スケーラブルではありません。

これを行うにはもっと速い方法があると思いますが、私が見つけたすべての例は文字列または整数を使用しています。

これを高速化するために推奨されるアルゴリズムや方法はありますか？

4

3 に答える 3

2

この回答は、順序は重要ではなく、オブジェクトから一意のキーを作成できるという前提に基づいています。

配列aからオブジェクトcにすべてのnエントリをコピーし、一意のキーを作成します。その後、配列bからそのオブジェクトにすべてのmエントリをコピーし（これにより、重複が自動的に削除されます）、次のようになりますO(n+m)。

var a = [{"Start": 1, "End": 2}, {"Start": 4, "End": 9}];
var b = [{"Start": 4, "End": 9}, {"Start": 3, "End": 12}];

var c = {};
a.forEach(function(el){c[el.Start+".."+el.End] = el});
b.forEach(function(el){c[el.Start+".."+el.End] = el});

console.log(c);
// yields: {"1..2":{"Start": 1, "End": 2},"4..9":{"Start": 4, "End": 9},"3..12":{"Start": 3, "End": 12}}

このオブジェクトのこの表記は少し冗長ですが、2つの配列をマージするのは非常に高速です。たぶん、これはさらに改善される可能性があります。

于 2013-02-01T16:45:51.750 に答える
1

最初にオブジェクトを低から高に並べ替えます。O(n log n)クイックソートで。

次に、この並べ替えを利用して、の1つのループで両方の配列をループすることができるプルーニングアルゴリズムを作成できますO(2n)。

元の配列とプルーニングされた配列をマージします。

JavaScriptのオブジェクトには順序がないことに注意してください。ただし、オブジェクトを並べ替えることはできません。配列に変換し、参照を保持して並べ替えます。

于 2013-02-01T16:26:02.120 に答える
0

私はjavascriptに精通していないので、これが実行可能かどうかは100％わかりません（オブジェクトの同等性などを比較する微妙な点についてはわかりません）が、javaまたは他の言語では、次のように機能する可能性があります。

  • 最初の配列を繰り返します。
  • 各要素について、キーがオブジェクトで値がカウントである「カウンター」ハッシュマップに格納されます。

この最初のパスの後、次のようになります。

{{"Start": 1, "End": 2}:1, {"Start": 4, "End": 9}:1, {"Start": 12, "End": 16}:1, ... }
  • 次に、2番目の配列を繰り返し処理します
  • 各要素について、カウンターハッシュマップ内の現在の要素を検索します。
  • カウンターハッシュマップに現在の要素と一致するキーが含まれている場合、それは重複しています
  • それ以外の場合は、最初の配列に追加します。

最初に並べ替えるよりも少し速いかもしれません（オブジェクトをキーとして使用できる場合）？

于 2013-02-01T16:36:54.017 に答える