2つのソートされた配列で共通の要素を見つける方法
1. 序章
このチュートリアルでは、2つのソートされた配列で共通の要素を見つける方法を説明します。
2. 2つのソートされた配列の共通要素
この問題では、2つのソートされた配列があります:と。 私たちの仕事は、共通の要素を見つけることです。
たとえば、との場合、アルゴリズムは結果として出力する必要があります。
共通の要素を効率的に見つけるには、とがすでに並べ替えられているという事実を使用する必要があります。 さらに、出力配列が入力配列として非降順である必要もあります。
また、とは重複を含む可能性があると想定します。 したがって、共通の要素がで2回、で3回繰り返される場合、結果の配列に2回含めます。 例えば:
3. 線形時間での共通要素の検索
とがソートされているという事実を使用しない単純なアルゴリズムから始めましょう。
それぞれについて、アルゴリズムは全体を繰り返し処理して、をチェックします。 したがって、時間計算量があります。これは、とが比較可能かどうかを意味します。 共通の要素をより速く取得するために、このアルゴリズムで何を変更できますか?
3.1. 線形探索
ええと、配列はソートされているので、。の場合、繰り返しても意味がありません。それぞれが。より大きいので、と結論付けることができます。 逆もまた真です。もし、なら、捨てることができます。
このようにして、各配列を1回だけ繰り返します。 したがって、ネストされたループは必要ありません。 代わりに、とで始めることができます。 の場合、。をインクリメントして破棄します。 同様のことがifにも当てはまります。 の場合、結果の配列に追加し、両方のカウンターを更新します。 またはの終わりに達すると、ループは停止します。 このアプローチは、マージソートアルゴリズムのマージステップに似ています。
その結果、アルゴリズムの時間計算量は線形になります。
3.2. 例
上記の例を使用して、アルゴリズムがどのように機能するかを示しましょう。
最初は、は空で、両方とも最初の要素を指しています。
以来、インクリメントします:
これで一致が得られたので、両方のカウンターに2を追加してインクリメントします。
もう一度一致するので、前の手順と同じようにします。
さて、それで私たちは捨てて次に進みます:
状況は同じ()なので、インクリメントするのは:だけです。
なので、インクリメントするのは:
新しい共通要素が見つかったので、それを追加して両方のカウンターをインクリメントします。
最後に、、停止して結果を出力します。
4. 対数時間で共通の要素を見つける
それを仮定しましょう。 次に、ごとに、対数二分探索で検索できます。ので、二分探索がの-番目の位置で見つかった場合、左側のすべての要素を破棄して、で検索できます。残り:。
同様に、バイナリ検索がで見つからないが、最後にチェックインするインデックスがであるとします。 の場合、で検索します。 一方、の場合でも、それが発生する可能性があるため、を破棄しません。
4.1. 擬似コード
上記のアルゴリズムの仕組みは次のとおりです。
最悪の場合の時間計算量はです。 の場合、はに関して定数であると見なすことができます。 その場合、アルゴリズムはおおよその複雑さを持ちます。ただし、の場合、アルゴリズムを取得します。 これは、単純なアプローチよりも優れていますが、両側線形探索の実行時間よりも劣っています。
5. 結論
この記事では、2つのソートされた配列の共通要素を見つける2つの効率的な方法を紹介しました。 1つのアプローチは複雑ですが、もう1つのアプローチは、バイナリ検索と線形検索を組み合わせて、一度に実行します。