2つのリスト

Question

の順序はリスト1

リスト1に一致するように並べ替えリスト2のためのO（N^2）より良いアルゴリズムがあります比較します注：リスト2は、リスト1と比較して、より多く、少ない、または全く異なるアイテムを持つことができます。

Answer 1

リスト内のアイテムのタイプの合計順序を作成できる場合は、リスト1のインデックスを作成できます。アイテムをソートする。その後、このインデックスを使用してリスト2を並べ替えることができます。このアルゴリズムは時間的にはO（n log n）であり、スペースには余分なO（n）が必要です。

Answer 2

O（n Log（n））となる可能性は次のようになります。リストの値を構造体の配列/ベクトル/ソート可能な型に読み込む必要があります。

• 値に基づいてリストをソートし、位置情報を保持します。これは、アイテムをルックアップし、その位置を知るための素早い方法を提供します。並べ替えのコストはO（n log n）
• です。並べ替えリスト2は、最初の手順の並べ替えられたリストを比較関数として使用します。 2つは2つの値を比較し、ソートされたリスト1の結果でそれらを検索し、2つの値の比較として相対位置を使用します。このソートのコストもO（n log n）です。

編集後、2番目のリストには最初のリストとの関連性がない可能性があります。したがって、比較関数はそれを考慮する必要があります。比較されている一方または両方の値が最初のリストにない場合、比較関数は値の順序を決定する必要があります（たとえば、最後または最初に行くのですか？）。

Answer 3

あなたはDiff Algorithmをお探しですか？