2次元アレイ円回転アルゴリズム？

Question

与えられたNxN 2次元配列。 1要素を時計回りに回転させる（ほぼ回転する）関数を書く。

[1][2][3][4] 
[5][6][7][8] 
[9][0][1][2] 
[3][4][5][6] 

次のようになります。

[5][1][2][3] 
[9][0][6][4] 
[3][1][7][8] 
[4][5][6][2] 

更新： これはオンライン面接の質問だった - HackerRank。私はそれを解決することができませんでした。これまでStackOverflowで見つかったのは90度回転です（この質問がどこかで見つかった場合は、コメント内のリンクを共有してください）。

Answer 1

明白な解決策がうまく機能として、私は、あなたが遭遇した問題の種類が非常によく分からない：

元の配列：

final int[][] a = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 0, 1, 2}, {3, 4, 5, 6}}; 

回転：

for (int i = 0; i < (a.length >>> 1); i++) { 
    final int minx = i; 
    final int miny = i; 
    final int maxx = a.length - 1 - i; 
    final int maxy = a.length - 1 - i; 

    int incx = 1, incy = 0; 
    int prev = a[miny][minx]; 
    for (int x = (minx + 1), y = miny; ((x != minx) || (y != miny)); x += incx, y += incy) { 
     final int temp = a[y][x]; 
     a[y][x] = prev; 
     prev = temp; 
     if ((x == maxx) && (incx == 1)) { 
      incx = 0; 
      incy = 1; 
     } 
     if ((y == maxy) && (incy == 1)) { 
      incx = -1; 
      incy = 0; 
     } 
     if ((x == minx) && (incx == -1)) { 
      incx = 0; 
      incy = -1; 
     } 
    } 
    a[miny][minx] = prev; 
} 

出力：

5 1 2 3 
9 0 6 4 
3 1 7 8 
4 5 6 2 

Answer 2

もう1つJavaのolution。

行と列の距離は計算されずに宣言されます。

final int[][] a = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 0, 1, 2 }, 
       { 3, 4, 5, 6 } }; 

final int[][] dRow = { { 1, 0, 0, 0 }, { 1, 1, 0, -1 }, 
       { 1, 0, -1, -1 }, { 0, 0, 0, -1 } }; 
final int[][] dCol = { { 0, -1, -1, -1 }, { 0, 0, -1, 0 }, 
       { 0, 1, 0, 0 }, { 1, 1, 1, 0 } }; 

int[][] tmp = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, 
       { 0, 0, 0, 0 } }; 

// rotate a to tmp 
for (int row = 0; row < a.length; row++) 
    for (int col = 0; col < a[row].length; col++) 
     tmp[row][col] = a[row + dRow[row][col]][col + dCol[row][col]]; 

// copy tmp to a 
for (int row = 0; row < a.length; row++) 
    for (int col = 0; col < a[row].length; col++) 
     a[row][col] = tmp[row][col]; 

// show result 
for (int row = 0; row < a.length; row++) 
    for (int col = 0; col < a[row].length; col++) 
     System.out.print((col == 0 ? "\n" : "") + a[row][col]); 

Answer 3

私はすぐに、正方行列（あなたはNxNを指定しました）のためのPythonで少し違ったアプローチをしました。各レイヤーに対して、私は展開し、回転して再適用します。これはで、確かによりも多くの作業が必要ですが、トレースしやすく、論理的に感じられました。

def rotate_matrix(m, n): 
    assert len(m) is len(m[0]), 'Assertion: rotation requires square matrix' 

    rotated_matrix = [[None] * len(m[0]) for _ in range(len(m))] 

    def _rotate_layer(ns): 
     return ns[n:] + ns[:n] 

    def _nth_layer(l): 
     left = [m[i][l-1] for i in range(l-1, len(m)-(l-1))] 
     bottom = m[len(m)-1-(l-1)][l:len(m)-(l-1)] 
     right = [m[i][len(m[0])-l] for i in reversed(range(l-1, len(m)-l))] 
     upper = m[l-1][len(m[0])-l-1:l-1:-1] 
     return left + bottom + right + upper 

    def _apply_layer(l): 
     ns = _rotate_layer(_nth_layer(l)) 
     for i in range(l-1, len(m)-(l-1)): 
      rotated_matrix[i][l-1] = ns.pop(0) 
     for i in range(l, len(m)-(l-1)): 
      rotated_matrix[len(m)-1-(l-1)][i] = ns.pop(0) 
     for i in reversed(range(l-1, len(m)-l)): 
      rotated_matrix[i][len(m[0])-l] = ns.pop(0) 
     for i in reversed(range(l, len(m[0])-l)): 
      rotated_matrix[l-1][i] = ns.pop(0) 

    for i in range(1, len(m)/2+1): 
     _apply_layer(i) 

    return rotated_matrix