algorithm - 2 つの数値リストが等しいかどうかを確認する

Question

数値の 2 つのリスト A、B が与えられます。それらが O(N^2) ソリューションと等しいかどうかを確認するより良い方法はありますか?

score 4 · Accepted Answer

2 つのリストを並べ替えるO(nlogn)
次に、両方を同時に調べて、同じ数値が含まれていることを確認しますO(n)

合計: O(nlogn)

score 1 · Accepted Answer

順序に関係なく、両方のリストに同じ番号が含まれている場合は、次のO( n *log n )アルゴリズムを使用できます。

ステップ(1)は2 * O( n *log n ) = O( n *log n )時間がかかります。2 番目のステップは線形O(n)時間で実行されます。

したがって、上記のアルゴリズムを実行すると、問題がO( n *log n )時間内に解決されます。

score 1 · Accepted Answer

まず、長さが等しいかどうかを確認します。そうであれば、A の数を HashSet に入れることができます。B を反復処理し、HashSet に存在するかどうかを確認します。そこにある場合は、HashSet から削除できます。最終的に HashSet が空の場合、それらは等しいです。これは O(n)

実際には、HashSet では重複が許可されていないため、キーを数値、値をカウントとする HashMap を使用できます。アルゴリズムは同じままです。B の数が HashMap で検出されるたびに、カウントが減少します。最終的に HashMap が空の場合、それらは等しいです。これもO(n)です。

score 0 · Accepted Answer

数値がリストでソートされ、両方のリストの長さが同じであると仮定します。

bool eq = true;

for (int i = 0; i < list1.length; i++) {
    if (list1[i] != list2[i]) {
        eq = false;
        last;
    }
}

4 に答える 4