2

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

O(n)数値の 2 つの配列 (正、負、または繰り返しを含むことができます) が、時間の複雑さとO(1)空間の複雑さにおいて互いの順列であるかどうかを判断する方法はありますか? スペースの制約が厳しいため、解決できませんでした。

4

2 に答える 2

2

数値が整数の場合、インプレース基数ソートO(nlogk)で時間が得られます。kは数値の範囲で、nは要素の数です。
アルゴリズムにはO(logk)、再帰呼び出しのスタック トレース用にスペースが必要であることに注意してください。 定数(たとえば2 ^ 64)に
バインドできる場合-スペースで時間を取得します。kO(n)O(1)

並べ替え後、両方の配列を単純に反復処理して、それらが同一かどうかを確認できます。

于 2012-07-15T08:09:03.613 に答える
0

数値自体の範囲に厳しい制限がある場合に実行できます。

たとえば、2つの配列AとBがあり、数値が-128と+127(8ビット符号付き)の間にバインドされていることがわかっているとします。256の場所の配列があるだけです。各番号nは場所にマップされますn + 128

両方の配列を反復処理します。配列Aの場合は対応する位置をインクリメントし、配列Bの場合はデクリメントします。次に、すべての場所が0であるかどうかを確認します。そうである場合、配列は順列ですが、そうでない場合はそうではありません。

時間計算量はO(n+k)です。スペースの複雑さはO(k)k数値の範囲です。はからk独立しnているので、それは、に関する限り、O(n)そしてあなたがにバインドされている限りです。O(1)nk

O(n)時間計算量は、の代わりに単純にさらに減らすことができることにも注意してくださいO(n+k)。ゼロ以外のカウントを持つ数値の現在の合計を保持するだけです。インクリメント/デクリメントがカウントを他の何かにプッシュするたびに、現在の合計をインクリメントします。ゼロにプッシュされるたびに、合計をデクリメントします。最後に、合計が0の場合、すべてのカウントは0です。

編集:アミットの答えはおそらくより良いスペースの複雑さを持っていますが:)

PS:ただし、このアルゴリズムは、数値の配列がストリーミングされる場合に適用できるため、実際にすべてをメモリに保持する必要はありません。したがって、条件が正しければ、完全な並べ替えよりもスペースの複雑さが小さくなる可能性があります

于 2012-07-15T08:12:25.500 に答える