0

n 要素の 1 次元配列が与えられた場合、配列の要素が左 m 位置になるように配列を効率的に回転するにはどうすればよいでしょうか? 定数 O(1) メモリのみを使用して O(n) 時間の複雑さでこれを行うことは可能ですか?

たとえば、n=8 で配列が[0, 1, 2, 3, 4, 5, 6, 7]m=2 だけ左に回転すると、 が得られ[2, 3, 4, 5, 6, 7, 0, 1]ます。

これは、私が実装した Python の単純なソリューションで、一時配列で O(n) 時間と O(n) メモリを使用します。

def rotateLeft(A, m):
    temp = [None]*len(A)
    for i in xrange(len(temp)):
        temp[i] = A[(i + m) % len(A)]
    for i in xrange(len(A)):
        A[i] = temp[i]

どうすればこれをより効率的に行うことができますか? これは、一定量のメモリで、まだ O(n) 時間で実行できると言われました。

どの言語での解決策も問題ありません。提案は大歓迎です。

編集: ライブラリ ソリューションを探しているわけではありません。さらに、配列はリンクされたリスト/両端キューではありません。head/tail/next/previous 要素の概念はありません。

4

5 に答える 5

7

逆の最終配列を見てみましょう。

[1, 0,    7, 6, 5, 4, 3, 2]    (spacing mine)

何か面白いものが見えますか？

于 2013-10-08T08:12:42.850 に答える
5

このようなソリューションがどのように見えるかを考えてみてください。これ以上スペースを使用できない場合、利用できる唯一の方法は要素を交換することです。ペン、2 つの要素の配列、次に 3 つの要素の配列を使って試してみてください。アイデアが得られたら、それは非常に簡単なはずです。

実際、スワップを使用するにはもう 1 つの変数が必要です。XOR スワップ アルゴリズム ( http://en.wikipedia.org/wiki/XOR_swap_algorithm ) を使用してこれを修正できますが、これは本当に重要ではないと思います。

于 2013-10-08T07:34:12.240 に答える
1

これは、メモリの制約により簡単ではありません。最初の要素を新しい場所に移動することから始めます。あまりにも多くの要素を格納することはできないため、削除した要素の場所を探し続けます。

ここで、パスの数が GCD(n,m) にどのように関連しているか、およびアルゴリズムがそれをどのように反映するかを考えてみましょう - gcd が 1 である一般的なケースから始めます (たとえば、上記の例で m=3 の場合)。一連の置換が終了すると (現在のインデックスと最初に使用したインデックスを比較することで確認できます)、タスクは完了です。ただし、GCD(m,n) > 1 の場合、要素の一部のみを移動したことになり、最後に開始した要素の直後に要素を使用して新しいチェーンを開始する必要があります。

ここで、フェーズの数に関係なく、実行されるシフトの総数が O(n) であることを確信してください。

于 2013-10-08T08:01:18.117 に答える
0

これは、@MBo からヒントを得たコンスタント メモリ ソリューションの 1 つです。i配列スペースと m: 、midpoint、およびに加えて、3 つの追加変数を使用しますendpoint。3 回ループします。最初に 2 つの部分配列を反転し、最後のループで配列全体を反転します。それは O(n/2 + m/2 + (nm) /2) であり、これは 0 <= m < n なのでm = m % n、最初に与えられた正の m を任意の正の m に減らすために行うため、O(n) です。配列の範囲内のインデックス。

スワッピングも 2 アイテム バッファ (2 要素のタプル) を介して値を送信しますが、これはスワップ用の定数メモリであるため問題ありません。

def rotateLeft(A, m):
    m %= len(A)
    # Reverse A[0..m-1]
    midpoint = m/2
    endpoint = m-1
    for i in xrange(midpoint):
        A[i], A[endpoint-i] = A[endpoint-i], A[i]
    # Reverse A[m..n-1]
    midpoint = m+(len(A)-m)/2
    endpoint = len(A)-1
    for i in xrange(m, midpoint):
        A[i], A[endpoint-(i-m)] = A[endpoint-(i-m)], A[i]
    # Reverses all elements of array in place
    midpoint = len(A)/2
    endpoint = len(A)-1
    for i in xrange(midpoint):
        A[i], A[endpoint-i] = A[endpoint-i], A[i]

また、負の回転 (右への回転) も可能で、これは私の意見では非常に優れています。これはrotateRight、次の方法で実装できることを意味します。

def rotateRight(A, m):
    rotateLeft(A, -m)

そして、次のコードはアサーション チェックに問題なくパスします。

A = [0, 1, 2, 3, 4, 5, 6]
B = A[:] # Make copy of A and assign it to B
rotateLeft(A, 4)
rotateRight(A, 4)
assert(A == B)
于 2013-10-08T09:36:14.870 に答える
0

次の PseudoCode を見てください。私には正しいようです。

    function rotate(a[], a.length)
    {
     i = 0; 
     j = 0;
     k = 0; 
     temp = a[0];
     k = (i + a.length - 2 ) % a.length
     while (j < a.length){
     temp1 = a[k]
     a[k] =  temp;
     i = k;
     temp = temp1
     k = (i + a.length - 2 ) % a.length         
     j++
     }

     }
于 2013-10-08T09:02:04.787 に答える