5

重複の可能性：
2つのソートされた配列の共通部分

2つのソートされた配列AとBがあり、1つを他の配列のすべての要素と比較する以外に、共通の要素を持つ配列を見つけるための最良のアルゴリズムを設計するにはどうすればよいですか？

4

3 に答える 3

32

各配列に 1 つずつ、合計 2 つのポインターを保持します。

i <- 0, j <- 0
repeat while i < length(arr1) and j < length(arr2):
    if arr1[i] > arr2[j]: increase j
    else if arr1[i] < arr2[j]: increase i
    else : output arr[i], increase both pointers

アイデアは、データがソートされている場合、要素が1つの配列で「大きすぎる」場合、配列に残っている他のすべての要素にとって「大きすぎる」ということです-ソートされているためです。

このソリューションでは、データを 1 回トラバーサルする必要があります。O(n)（良い定数も）。

于 2012-10-20T23:43:07.667 に答える
10

2 つの配列 (たとえば、要素をA持っているものと要素を持っているもの) の長さが類似している場合、最善の方法は、1 つの配列の要素を別の配列で線形検索することです。もちろん、配列はソートされているため、次の検索は前の検索が停止した場所から開始する必要があります。これは、「並べ替えられた配列のマージ」アルゴリズムで使用される古典的な原則です。の複雑さ。NBMO(N + M)

長さが大幅に異なる場合 (たとえば、M << N)、より最適なアプローチは、短い配列の要素を反復処理し、バイナリ検索を使用して長い配列でこれらの値を探すことです。複雑なのはO(M * log N)その場合です。

ご覧のとおり、 は よりもはるかに小さい場合O(M * log N)よりも優れており、そうでない場合はさらに悪くなります。O(N + M)MN

あるアプローチから別のアプローチへの切り替えをトリガーする必要がある配列サイズの違いは、いくつかの実際的な考慮事項に依存します。データを使った実際の実験に基づいて選択する必要があります。

これら 2 つのアプローチ (線形検索と二分検索) は、1 つのアルゴリズムに "ブレンド" できます。と仮定しましょうM <= N。その場合はstep valueを選択しましょうS = [N / M]。配列から最初の要素を取得し、ステップで配列内のその要素に対してまたがる線形検索をA実行します。つまり、要素などをチェックします。検索対象の要素を含む可能性のあるインデックス範囲が見つかったら、 array のそのセグメント内でバイナリ検索に切り替えます。終わり。の次の要素のまたがる線形検索は、前の検索が中断されたところから始まります。(ちなみに、BSB[0], B[S], B[2*S], B[3*S], ...[S*i, S*(i+1)]BAS2 のべき乗に等しい)。

この「混合」アルゴリズムは、存在する 2 つの並べ替えられた配列に対して最も漸近的に最適な検索/マージ アルゴリズムです。ただし、実際には、配列の相対的なサイズに応じてバイナリ検索または線形検索のいずれかを選択する、より単純なアプローチは完全にうまく機能します。

于 2012-10-20T23:57:34.280 に答える
1

1つを他の配列のすべての要素と比較するだけでなく

A[] と B[] を比較して、それらが同じであることを確認する必要があります-保持できるデータの種類についてよく知っていない限り。比較の性質にはおそらく多くの解決策があり、必要に応じて最適化できます。

配列が非常に厳密に作成されている場合、つまり、既知のパターンの連続した値のみで、常に既知のポイントから開始する場合、各配列の長さを見て、すべての項目が共通であるかどうかを知ることができます。

残念ながら、これは非常に現実的または有用な配列のようには聞こえないため、B[] 内の A[i] のチェックに戻ります。

于 2012-10-20T23:51:24.377 に答える