$ mathcal {o}（n log n）$のリンクリストをパージする方法は？

Question

$ mathcal {o}（n lg n）$ timeのリンクリストから重複値を削除する方法を疑問に思っていました。ポインターの平等な進歩であり、1つの要素を考慮した場合、小さな要素を選択するために要素を比較するときにマージソートを使用することにより、私は考えています。代替品はありますか？

Answer 1

1. リンクリストを$ o（n log n）$ timeで並べ替えます。
2. リストの各要素を順序で通過し、$ o（n）$ timeの前の要素と同じ場合、要素を削除します。

合計の複雑さは$ o（n log n）$です。これはあなたが探しているものです。

Answer 2

次のように$ o（n）$で行うことができます。

1）リンクリストを通過し、その要素をハッシュテーブルに追加することにより、ハッシュテーブルを構築します。各反復で、ハッシュテーブルを検索して、イテレーションで考慮されている現在の要素を検索します。要素が見つからない場合は、ハッシュテーブルに要素値をキーとして、1を対応する値として追加します。代わりに、要素を見つけた場合（前の反復に挿入された）、対応する値に1を追加してハッシュテーブルエントリを更新します（要素の多重度を正しく更新します）。最後に、ハッシュテーブルにはせいぜい$ n $エントリが含まれます（これは、リンクリストの要素が異なる場合に対応します）、または$ n $要素未満で、少なくとも1つのエントリは多重性を示しています1つ以上。ハッシュテーブルで行われた作業が$ o（1）$である$ n $ iterationsのそれぞれで$ o（n）$の時間がかかります。

2）ここで、ハッシュテーブルをトラバースし、見つかった各要素のノードを追加して新しいリンクリストを作成します。ハッシュテーブルには最大$ n $要素が含まれているため、最大で$ o（n）$がかかります。ハッシュテーブルの各要素で行われた作業は$ o（1）$で、新しいリストにノードを追加するには$ oが必要です（1）$。

したがって、総複雑さは最大で$ o（n）$です。