リストの交差点を見つけるための効率的な方法
1. 概要
このチュートリアルでは、リンクリストの共通部分を見つける方法について説明します。 最初に、2つのリストの共通部分を見つけるためのさまざまなアプローチについて説明します。
その後、これらのアプローチを一般化して、複数のリストの共通部分を見つける方法を示します。
最後に、説明したアプローチ間の主な違いを示す比較で終わります。
2. 定義
複数のリストの共通部分を定義する必要があります。 次の例を見てみましょう。
この例では、、、およびの3つのリストがあります。 また、前の3つの共通部分を表すがあります。
複数のリストの共通部分を計算するには、それらの間の相互要素を決定する必要があります。 上記の例では、相互の要素は赤い色でマークされています。
ここで注意すべきことの1つは、値が複数回繰り返される場合です。 この場合、結果には最小の繰り返し回数でそれが含まれている必要があります。 たとえば、値がで2回、で3回、で2回繰り返される場合、その値は2回含まれます。
したがって、問題は、いくつかの特定のリストの共通部分を見つけることになります。 簡単にするために、最初に2つのリストの場合の問題を解決するための多くのアプローチについて説明します。
その後、説明したすべてのアプローチを一般化して、複数のリストを処理できるようにする方法を説明します。
3. 素朴なアプローチ
素朴なアプローチでは、最初のリストのすべての要素を繰り返し処理します。 各要素について、2番目の要素の内部に存在するかどうかを確認します。
素朴なアプローチの実装を検討してください。
まず、問題の答えを保持する空のリストとして定義します。 また、の先頭を指すイテレータを設定します。
その後、のすべての要素を繰り返し処理します。 要素ごとに、同じ値の要素が含まれているかどうかを確認します。 その場合、結果のに要素を追加します。
また、から要素を削除します。 関数はから要素の最初の出現のみを削除する必要があることに注意してください。 その理由は、要素がとの両方で2回以上繰り返された場合、に2回追加する必要があるためです。
要素のチェックが完了したら、イテレータを次の要素に移動します。
最後に、結果のを返します。
素朴なアプローチの複雑さはです。ここで、はの要素の数であり、はの要素の数です。
その理由は、ソートされていないためです。 したがって、各要素の存在を確認するために線形探索を実行する必要があります。
4. より速いアプローチ
4.1. 一般的なアイデア
素朴なアプローチでは、要素がその中に存在するかどうかを見つけるために、内部で線形探索操作を実行しました。 この検索を改善する方法を考えてみましょう。
内部の要素をTreeSetに追加して、その内部でクイック検索を実行できます。 ただし、これにより、繰り返される要素が1回だけ追加されます。 したがって、繰り返される要素の場合を処理することはできません。
もう1つの方法は、内部のすべての要素をTreeMapまたはHashMapに追加することです。 このチュートリアルでは、TreeMapを使用します。
アイデアは、内の各要素の繰り返し数を計算することです。 たとえば、値5が内部で3回繰り返される場合、はになります。
これで、繰り返しをチェックすることで、内部の値の存在を簡単にチェックできます。 繰り返しがゼロより大きい場合、値が存在し、それを回答に追加できます。
また、から値の最初の出現を削除することも簡単になります。から要素を消去するには、その繰り返しを1つ減らします。
4.2. 実装
より高速なアプローチの実装を見てみましょう。
素朴なアプローチと同様に、問題に対する結果の回答を保持する空のリストを初期化します。 また、マップをゼロで初期化します。 その理由は、ある値の繰り返しを検索する場合、それがまだ追加されていない場合、マップはデフォルト値であるゼロを返す必要があるためです。
次に、内のすべての要素を繰り返し処理します。 要素ごとに、マップ内でその値の繰り返しを1つ増やし、次の要素に移動します。
その後、内のすべての要素を繰り返し処理します。 各要素について、内部の値の繰り返しがゼロより大きいかどうかを確認します。 もしそうなら、それを結果に追加し、その繰り返しを1つ減らします。 また、イテレータを1ステップ進めて、次の要素に到達します。
最後に、結果のを返します。
このアプローチの複雑さはです。ここで、は最初のリスト内の要素の数であり、は2番目のリスト内の要素の数です。
大きい方のリストをマップに追加し、小さい方のリストを反復処理することが常に最適であることに注意してください。理由は。
5. 特殊なケース
問題のいくつかの特殊なケースについて説明しましょう。 より高速なアプローチの方が複雑であるため、単純なアプローチではなく、それに対する改善点について説明します。
5.1. 小整数アプローチ
リスト内の要素が小さな整数値であると仮定します。 この場合、TreeMapを使用する必要はありません。 代わりに、サイズの配列を使用できます。ここで、はとの内部の最大値です。
したがって、アルゴリズム2内の変数は、TreeMap ではなく、配列である必要があります。 初期化するには、この配列内のすべての要素をゼロで初期化する必要があります。 その後、の要素を繰り返し処理し、その値の繰り返しを1つ増やします。
現在は配列になっている概念を除いて、実装は同じままです。
リストの1つに他のリストよりも小さい値が含まれている場合は、この配列の繰り返しを計算するのが最適であることに注意してください。 その理由は、の値が小さくなるためです。
また、アルゴリズムを少し更新する必要があります。 の要素を反復処理するときに、要素の1つが。より大きい場合、その繰り返しをチェックせずにすぐに続行します。 その理由は、その繰り返しが確実にゼロになるためであり、配列の範囲外に出たくないからです。
このアプローチの複雑さはです。ここで、は最初のリストのサイズ、は2番目のリストのサイズ、はいずれか小さい方のリストの最大値です。
5.2. ソート済みリストアプローチ
2番目の特殊なケースは、両方のリストがソートされている場合です。 この場合、まったく新しいアプローチを考え出すことができます。
両方のリストを同時に繰り返します。 各ステップで、値が小さいイテレータのイテレータを移動します。 両方のイテレータが同じ値に達した場合、それを結果に追加し、両方のイテレータを移動します。
このアプローチの実装を見てみましょう。
前と同じように、空のリストを初期化して、結果の回答を含めます。 ただし、このアプローチでは、2つのイテレータを取得し、との両方を反復処理します。
各ステップで、小さい値を指すイテレータを進めます。 それでも、両方のイテレータが値が等しい2つの要素を指している場合は、この値を結果に追加して、両方のイテレータを移動します。
このアプローチの背後にある考え方は、両方のイテレータが異なる値を指している場合、それらの1つを移動する必要があるということです。 ただし、両方のリストがソートされているため、小さい方の値はもう一方のリスト内に見つかりません。 その理由は、もう一方のイテレータがすでに大きな値を指しているためです。
したがって、小さい値を指すものを移動することが常に最適です。
このアプローチの複雑さはです。ここで、は最初のリスト内の要素の数であり、は2番目のリスト内の要素の数です。
6. 複数のリストの共通部分
3つ以上のリストが与えられ、それらすべての共通部分を計算する必要がある場合は、前述のアプローチのいずれかを更新できます。
最初に、説明したアプローチのいずれかを使用して、最初の2つのリストの共通部分を計算できます。 次に、結果と3番目の結果の交差を計算できます。
この操作は、最終結果に到達するまで続きます。
たとえば、3つのリストがあり、並べ替えられたリストのアプローチを使用できた場合、複雑さは次のようになります。ここで、は最初のリストのサイズ、は2番目のサイズ、は3番目のサイズです。
7. 比較
以前に説明したすべてのアプローチの比較を見てみましょう。
メモリの複雑さは、アルゴリズムによって割り当てられた追加のメモリを表すことに注意してください。 したがって、両方のリストによって割り当てられたメモリについては説明していません。
ご覧のとおり、一般的なケースでは、複雑さが低く、両方のリストですでに消費されているメモリよりも大きなメモリを消費しないため、より高速なアプローチを使用することを常にお勧めします。
ただし、小整数アプローチとソート済みリストアプローチはどちらも、それぞれの特殊なケースで役立ちます。
リストの少なくとも1つの値が小さい場合は、小整数アプローチの使用を検討する必要があります。 ただし、この場合、のメモリを割り当てていることに注意する必要があります。 このアプローチを使用できるようにするには、このメモリを比較的小さくする必要があります。
一方、ソートされている場合は、複雑さが最も低く、余分なメモリを消費しないため、ソートされたリストのアプローチを使用する必要があります。
8. 結論
このチュートリアルでは、リンクリストの共通部分を見つける問題について説明しました。 まず、素朴なアプローチについて説明し、より良いアプローチを得るためにそれを改善しました。
次に、いくつかの特殊なケースを提示し、それぞれを実装するために必要な更新を示しました。
第三に、複数のリストの共通部分を取得するためにすべてのアプローチを更新する方法を説明しました。
最後に、説明したすべてのアプローチの主な違いをリストした比較表を使用して要約しました。
