c - リストから重複要素を削除する最も効率的な方法

Question

重複を削除したいソートされていないリストがあります。Cでこれを実行するのに最も効率的なのは何ですか。私の場合、リストは配列のリンクリストです。つまり、複数のアレイがリンクされています。重複は、異なる配列でのみ発生する可能性があります。たとえば、配列 1 内で重複することはできませんが、配列 1 と 2 で同じ数を見つけることができます。

Answer 1

これは基本的にElement Distinctness Problemの修正です。リンクは、いくつかの可能な解決策を通過します。

一般的で単純な解決策の 1 つは、リストを並べ替えて、並べ替えられたリストを通過させ、重複を削除することです。これにより、 O(n*log(n)) アルゴリズムが得られます

ハッシュテーブルを使用すると、(O(n)) をより適切に実行できます。配列を調べて、各要素をハッシュ テーブルに挿入します。衝突が発生した場合は、重複が見つかった可能性があり、これら 2 つの要素をすばやく比較できます。