リンクリストから重複を削除する
1. 概要
このチュートリアルでは、リンクリストから重複を削除する問題について説明します。 この問題には多くのバージョンがあります。 したがって、問題の一般的な考え方を説明してから、それを解決する素朴なアプローチについて説明します。
その後、素朴なアプローチを改善して、より高速なソリューションを取得します。 また、他のバージョンのいくつかを紹介し、それらを解決する方法について説明します。
最後に、提供されているすべてのアプローチの比較を示します。
2. 問題の定義
要素を持つリンクリストがあるとします。 そこから重複を削除して、一意の要素を持つ新しいリンクリストを取得します。
つまり、結果のリンクリストには、要素が2回以上繰り返されてはなりません。
3. 素朴なアプローチ
まず、素朴なアプローチについて説明します。
その実装を見てみましょう：
このアプローチでは、すでに追加されている各要素のすべての可能な値をチェックしています。 したがって、これをブルートフォースアプローチと呼びます。
まず、空のリストとして定義し、それを使用して結果のリンクリストを保存します。
次に、w
もしそうなら、私たちは答えに要素を追加しません。 そうでなければ、それは私たちがこの要素を見たのはこれが初めてであることを意味します。 したがって、それを回答に追加します。
最後に、重複のないリンクリストを返します。
単純なアプローチの複雑さはです。ここで、はリンクリストのサイズです。 その理由は、最悪の場合、すべての要素が異なるためです。 したがって、それぞれの取得されたすべての要素を反復処理する必要があります。
ただし、特殊なケースでは、すべての要素が等しい場合、一致する要素を見つけた後にチェックループを停止する break ステートメントのおかげで、複雑さが軽減されます。
4. より速いアプローチ
素朴なアプローチを改善してみましょう。
4.1. 一般的なアイデア
素朴なアプローチでは、
つまり、取得した要素を保持するためのデータ構造が必要です。 次に、このデータ構造を使用して、重複があるかどうかを確認します。
たとえば、 TreeSet データ構造は、その中の要素を追加および検索し、時間内に要素が含まれているかどうかを確認できるため、正しい選択です。
4.2. 実装
Fasterアプローチの実装を見てみましょう。
素朴なアプローチと同様に、最終的な答えを保持する空のリストとして定義します。 また、後で重複をチェックするために追加された要素を保持する新しい空のTreeSetとして定義します。
前と同じように、イテレータを使用して、のすべての可能な値を反復処理します。 ただし、このアプローチでは、データ構造を使用して、現在の要素と等しい以前に追加された値があるかどうかを確認しています。
データ構造内に要素が見つからない場合は、リストに追加する必要があります。 また、後で提示された場合に追加されないように、追加する必要があります。
最後に、重複のないリンクリストを返します。
より高速なアプローチの複雑さはです。ここで、はリンクリストのサイズです。
その理由は、最悪の場合、すべての要素が異なる場合、すべての要素をに追加する必要があるためです。 また、リスト内のすべての値をチェックする必要があります。
ただし、特殊なケースでは、すべての要素が等しい場合、複雑さはに減少します。 これは、の複雑さが、それに追加されたさまざまな要素の数によって影響を受けるためです。 この場合、それは1つの要素にすぎません。
5. 小整数値アプローチ
この特殊なケースでは、要素を含むという名前のリンクリストがあります。 各要素には、範囲内の整数値があります。
特定のケースでは、が比較的小さい場合、次のアプローチを使用してこの問題を解決できます。
- サイズが。の新しいブール配列を定義します。 それを呼び出して、この配列のすべての値を。で初期化します。
- 以前に値が追加されたかどうかを確認したい場合は、が追加されているかどうかを確認するだけで済みます。
- に値を追加するときは、に割り当てる必要があります。
実装がどのように見えるかを見てみましょう。
まず、結果の回答を保持する空のリストとして定義しましょう。 また、特定の要素の存在を確認するために使用される配列として定義しましょう。 この配列の初期値は。である必要があります。
次に、のすべての要素を繰り返し処理します。 各要素について、以前に現在の値を追加したかどうかを確認します。 これを行うには、配列を使用します。 以前にこの値を追加したことがない場合は、この値を追加して、の場所に割り当てる必要があります。
最後に、リンクリストを返します。
要素の範囲がであるような負の値がある場合でも、すべての値を。だけシフトした後でも、このアプローチを使用できることに注意してください。 したがって、配列の範囲はになり、要素の位置はになります。
このアプローチの複雑さはです。ここで、はリンクリストのサイズであり、は要素の最大値です。
6. ソートされたリンクリストアプローチ
リンクリストが並べ替えられたとします。 このソートを利用して、さらに高速なソリューションを取得しましょう。
6.1. 一般的なアイデア
リンクリストがソートされると、すべての等しい要素が互いに隣接します。 したがって、で重複をチェックする場合は、リストに最後に追加された要素をチェックするだけで十分です。
6.2. 実装
ソートされたリンクリストアプローチの実装を見てみましょう。
最初は、以前と同様に、空のリストとして定義しました。 次に、すべての要素を繰り返し処理し、現在の値が以前に追加されたかどうかを確認します。
その結果、以前に要素を追加したことがない場合、または最後に追加された要素と等しくない場合に、値を追加します。
このアプローチの複雑さはです。ここで、はリンクリストのサイズです。
7. 比較
以前のアプローチの違いを見てみましょう。
ご覧のとおり、単純なアプローチは実装が簡単で、理解しやすいものです。 ただし、時間の複雑さを考慮すると、一般に、より高速なアプローチの方が複雑さが低くなります。
ただし、リストがソートされる特殊なケースでは、複雑さが増すため、ソートされたリンクリストアプローチを使用することをお勧めします。
また、リスト内に小さな整数値がある場合は、小さな整数のアプローチを使用することをお勧めします。
8. 結論
このチュートリアルでは、リンクリストから重複を削除する問題について説明しました。
まず、素朴なアプローチを提示し、より高速なアプローチを得るためにそれを改善しました。 次に、2つの特殊なケースについて説明し、これらのケースで問題を解決する方法を示しました。
最後に、提示されたすべてのアプローチの概要を比較し、それぞれをいつ使用するかを示しました。
