2

サイズNの2つの整数配列が与えられた場合、一方が他方の順列であるかどうかを判断するアルゴリズムを設計します。つまり、それらにはまったく同じエントリが含まれていますが、場合によっては異なる順序で含まれていますか。

私は2つの方法を考えることができます：それらをソートして比較します：O（N.log N + N）

配列に同じ数の整数があり、これらの整数の合計が同じであるかどうかを確認してから、両方の配列をXORして、結果が0であるかどうかを確認します。これはO（N）です。この方法で誤検知が完全に排除されるかどうかはわかりません。考え。より良いアルゴリズム？

4

4 に答える 4

3

配列に同じ数の整数があり、これらの整数の合計が同じであるかどうかを確認してから、両方の配列をXORして、結果が0であるかどうかを確認します。

これは機能しません。例：

a = [1,6]  length(a) = 2, sum(a) = 7, xor(a) = 7
b = [3,4]  length(b) = 2, sum(b) = 7, xor(b) = 7

HashMap他の人はすでにO（n）ソリューションを提案しています。

Dictionary<T, int>これは、 ：を使用したC＃のO（n）ソリューションです。

bool IsPermutation<T>(IList<T> values1, IList<T> values2)
{
    if (values1.Count != values2.Count)
    {
        return false;
    }

    Dictionary<T, int> counts = new Dictionary<T, int>();
    foreach (T t in values1)
    {
        int count;
        counts.TryGetValue(t, out count);
        counts[t] = count + 1;
    }

    foreach (T t in values2)
    {
        int count;
        if (!counts.TryGetValue(t, out count) || count == 0)
        {
            return false;
        }
        counts[t] = count - 1;
    }

    return true;
}

CounterPythonでは、次のクラスを使用できます。

>>> a = [1, 4, 9, 4, 6]
>>> b = [4, 6, 1, 4, 9]
>>> c = [4, 1, 9, 1, 6]
>>> d = [1, 4, 6, 9, 4]
>>> from collections import Counter
>>> Counter(a) == Counter(b)
True
>>> Counter(c) == Counter(d)
False
于 2012-08-20T22:05:56.793 に答える
2

のスペースの複雑さがO(n)問題にならない場合はO(n)、最初にハッシュマップに最初の配列の各値の出現回数を格納し、次に2番目の配列で2回目のパスを実行して、すべての要素を確認することで、それを行うことができます。マップに存在し、各要素の出現回数を減らします。

于 2012-08-20T22:11:30.640 に答える
2

最善の解決策は、おそらく、キーが2つの配列の値であるマップを使用して1つを数えることです。

適切なマップ位置を作成/インクリメントする一方の配列を実行し、適切なマップ位置を作成/デクリメントするもう一方の配列を実行します。

結果のマップが完全にゼロで構成されている場合、配列は等しくなります。

これはO（N）であり、これ以上のことはできないと思います。

これは、マーク・バイアーズが彼の答えで目指していたものとほぼ同じだと思います。

于 2012-08-20T22:17:22.753 に答える
0

両方の配列の内容を数値で並べ替えてから、n番目の各項目を比較します。

array1の各アイテムを取得して、それがarray2に存在するかどうかを確認することもできます。あなたが見つけた一致の数を数えてください。最後に、一致の数は配列の長さと等しくなければなりません。

于 2012-08-20T22:08:49.817 に答える