Zweidimensionaler Array-Kreis-Rotationsalgorithmus?

Question

Gegeben NxN zweidimensionalen Array. Schreibe eine Funktion, die es um 1 Element im Uhrzeigersinn dreht (fast kreisende Bewegung).

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

Becomes:

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

Update: Das war ein Online-Interview-Frage - HackerRank. Ich konnte es nicht lösen. Alles, was ich bisher in StackOverflow gefunden habe, sind 90-Grad-Rotation (wenn Sie diese Frage irgendwo gefunden haben, teilen Sie bitte den Link in Kommentaren).

Answer 1

Ich bin mir nicht ganz sicher, welche Art von Problem, das Sie begegnet sind, als offensichtliche Lösung funktioniert gut:

Original-Array:

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

Rotation:

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; 
} 

Ausgang:

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

Answer 2

Weitere s Lösung in Java.

Die Zeilen- und Spaltenabstände werden eher deklariert als berechnet.

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

Ich habe dies schnell ein zu gehen, mit einem etwas anderen Ansatz in Python für quadratische Matrix (Sie NxN angegeben). Für jede Ebene entpacke ich, rotiere und trage sie erneut auf. Dies ist definitiv mehr Arbeit als nötig, aber war einfach zu verfolgen und fühlte sich logisch - und funktioniert für + -n Schritt Rotation.

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