5

重複の可能性:
配列 B が A の順列であるかどうかを確認する

2 つのソートされていない同じサイズのa整数配列が与えられます。が の順列であるbかどうかを判断します。これはおよびで実行できますか?baO(n) timeO(1) space

私の頭に浮かんだ最初の解決策はXOR、つまりを使用することですXOR all the elements of a and b and if the resultant is 0 which means that b is a permutation of a。しかし、彼はこのアプローチが失敗する例を挙げています。例えば ​​-

a: [1 6 0 0 4] -- b: [1 0 6 1 5]
a: [1 6 0 0 5] -- b: [1 0 6 1 4]

O(n) timeとでそれを行う方法について何か考えがある人はいますO(1) spaceか?

4

3 に答える 3

2

整数の制限された範囲の場合、その範囲を基数ソートを使用して配列をソートできるようにします[n,m]。これは、この素晴らしい投稿でも説明されています。m-n = U

2 つの並べ替えられた配列が得られた後 (両方を単純に繰り返すだけで答えが得られます)、並べ替えられた配列が同一である場合にのみ、元の配列は互いの順列になります。

注：
この回答にはいくつかの「不正行為」があります[したがって、OPがコメントで要求するまで投稿しませんでした..]、時間の複雑さは でありO(nlogU)、スペースはO(logU)です。ただし、境界のある範囲については、 を仮定できます。O(logU) = O(1)これらの場合、O(n)時間とO(1)空間が得られます。

于 2012-06-07T12:10:20.887 に答える
1

セット要素が非負であり、無制限の整数型 (aBigIntegerまたは類似の型) を使用できる場合は、 set に対して関数を定義できますA。

C(A) = product(p_(a+1)))それぞれaにA

は番目の素数ですp_n。n次に、順序ではなくの値Cのみに依存します。また、値を変更すると変更されます。AC

例えば、

C([1 6 0 0 4]) = p_2.p_7.p_1.p_1.p_5 = 3.17.2.2.11 = 2244

(そして明らかに、同じ要素を持つセットはC、順序に関係なく、同じ を持ちます)、および

C([1 6 0 1 4]) = p_2.p_7.p_1.p_2.p_5 = 3.17.2.3.11 = 3366

したがって、これらのセットが異なることがわかります。これは、1 より大きい整数は素数の一意の積 (因子の順序付けまで) として記述できるという算術の基本定理を使用します。あるいは、当然の結果を使用しているのかもしれません。この方法は私が作ったばかりなので、うまくいかないかもしれません。この投稿は、その正しさを証明しようとするものではありません...

于 2012-06-07T09:44:19.730 に答える
1

排他的 OR ソリューションは基本的にハッシュベースのソリューションですが、品質の低いハッシュ関数を使用しています。

あなたが欲しいのはハッシュ関数です...

  1. 衝突する可能性が非常に低いハッシュを与えるため、整数の一意の識別子として扱うことができます。Git は SHA-1 ハッシュを使用してソース コードのバージョンを識別します。衝突の可能性は非常に低く、無視できます。

  2. 交換可能 (xor や plus など) であり、おそらく連想的であるため、アイテムの順序によって結果のハッシュが変更されることはありません。

その 2 番目の要件は、おそらく厄介なものです。Google でしばらく過ごしましたが、「Quasigroup」などの単語が怖くなりました。

于 2012-06-07T12:33:47.380 に答える