2

整数の配列はほとんどありません。各配列の要素は順序付けられています。配列には重複がありません。

結果の配列には、すべての配列に存在する要素のみが含まれるように、すべての配列を 1 つに結合する必要があります。

たとえば、私は配列を持っています

(1,2,3,4,5) (2,3,5) (1,2,4,5)

結果は (2,5) でなければなりません

最高のパフォーマンスを達成するための最善の方法は何ですか?

4

3 に答える 3

9

配列に多くの異なる数値が含まれていると予想され、それらすべてに存在するのはごくわずかである場合、

  • 2 つの最小の配列を選択し、(マージソートのように) 順番にステップ実行して交差を計算します、O(len1 + len2)
  • すべての配列がスキャンされているわけではありませんが、次に小さい配列を選択し、以前に処理された配列の交点との交点を計算しlength(intersection)*log(length(array)) >= length(array)ますarray。

最悪の場合の複雑さは O(sum(lengths)) です。運が良ければ、 を回避できます。k * sum(log(length))ここkで、 は交差する要素の数です。

于 2012-10-02T22:20:01.077 に答える
4

これはうまくいくはずです：

  • 配列ごとに 1 つのインデックスを作成する
  • 各配列のそれぞれのインデックスの要素が同じ場合、その要素を結果リストに追加し、各インデックスを 1 ずつ増やします
  • それ以外の場合は、最も低い要素を指すインデックスを増やします
  • 最初の配列を超えるまで繰り返す

これは、配列が数値の複数のインスタンスを含むことができる場合にも機能するはずです。たとえば、配列 (1,1,2,2)、(2,2,3,3) は (2,2) になります。

于 2012-10-02T22:15:17.907 に答える
2

これが私の考えHashMap<Integer, Integer>ですnumer->hits。すべての配列を反復します:

  • 要素が hashMap に存在する場合、count(value) をインクリメントします。つまり、count++;
  • 要素が存在しない場合は、値に count = 1 を書き込みます

結局、number->count

1->1
2->3
3->2
4->2
5->3

したがって、HashMap を繰り返し処理して if(value==arrays.lenth) を出力します。

したがって、スペースは O(N) および O(N) ステップです。

ハッシュマップのアクセスは一定時間です(yahoooooo)。

于 2012-10-02T23:06:53.987 に答える