algorithm - 逆リストの和集合

Question

k個のソートされた逆リストを与えてください。これらのk個のリストの和集合を取得する効率的なアルゴリズムが必要ですか? 各インバーテッド リストはメモリ内の読み取り専用配列であり、各リストにはソートされた順序で整数が含まれます。結果は、十分な大きさの事前定義された配列に保存されます。k-way マージより優れたアルゴリズムはありますか?

Answer 1

K-Way マージが最適です。O(log(k)*n)ops [すべてのリストをn組み合わせた要素の数] があります。

@jpalecekが述べたように、それがうまくいかないことは簡単にわかります。それ以外の場合は、配列O(nlogn)をサイズ1のチャンク[逆インデックス]に分割するよりもうまくソートできます。

• 注：この回答は、逆インデックス[結果の配列]がソートされることが重要であると想定しています。この仮定は、特に情報検索領域で逆索引を使用するほとんどのアプリケーションに当てはまります。この機能 [並べ替えられたインデックス] により、インデックスをエレガントかつ迅速に交差させることができます。
• 注: 標準の k-way マージでは重複が許可されます。要素が 2 つのリストに表示されている場合は、一度だけ追加されることを確認する必要があります [追加する前にターゲット配列の最後の要素をチェックするだけで簡単に実行できます]。

Answer 2

結果の配列をソートする必要がない場合、最善の方法は、ハッシュ テーブルを使用して、どの要素を見たかをマークすることです。O(n)このようにして、 （n要素の総数である）時間の複雑さを得ることができます。

（Perl）の行に沿ったもの：

my %seen;
@merged = grep { exists $seen{$_} ? 0 : ($seen{$_} = 1) } (map {(@$_)} @inputs);