sorting - 別のリストで定義された順序に従ってリストを並べ替える

Question

リストAの要素を別の (スーパーセット) リストBの順序に従うように並べ替えるにはどうすればよいですか? 重複はないと仮定します。

たとえば、Aには [8 2 5 1] が含まれ、Bには [5 6 9 8 7 4 1 2 3] が含まれる可能性があるため、Aを [5 8 1 2] になるように並べ替えます。

これを効率的に実行し、実行時の複雑さを軽減する方法に興味があります。

score 3 · Accepted Answer

BがAのスーパーセットである場合、 Aをハッシュテーブルにダンプし、 Bをスキャンして、ハッシュテーブルに含まれるBのすべての要素を挿入する新しいリストを作成します。O（a）追加メモリとO（b）ランタイムを使用します。

score 2 · Accepted Answer

ここにいくつかのアイデアがあります：

(与えられた時間計算量では、nはAのサイズで、mはBのサイズです。時間計算量は単純化されていません。)

Bの各要素に対して、 Aの線形検索を実行して、その要素が存在するかどうかを確認します。その場合は、まだ配置されていないAの最初の要素と交換します。時間の複雑さ: O(nm)
上記と同じですが、最初にAの内容を効率的なルックアップ構造に入れ、線形検索を回避します。時間計算量: O(1) ルックアップを仮定すると O(n + m)
Bを並べ替えます。次に、A の各要素について、バイナリ検索を使用してB内のインデックス (存在することが保証されている) を見つけます。このインデックスをAと同じサイズの補助配列に記録します。そのインデックスの配列を、 Aを並べ替えるコンパレータへの入力として使用します。時間計算量: O((m log m) + (n log n) + (n log n))

2 に答える 2