Wie kann man ein zweidimensionales Feld drehen?

Question

Inspiriert durch Beitrag von Raymond Chen Wenn Sie ein zweidimensionales 4x4-Array haben, schreiben Sie eine Funktion, die es um 90 Grad dreht. Raymond verlinkt auf eine Lösung in Pseudocode, aber ich würde gerne etwas aus der Praxis sehen.

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

Wird:

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

Update : Die Antwort von Nick ist die einfachste, aber gibt es eine Möglichkeit, es besser zu machen als n^2? Was wäre, wenn die Matrix 10000x10000 wäre?

Answer 1

Hier ist meine Ruby-Version (beachten Sie, dass die Werte nicht gleich angezeigt werden, aber es dreht sich trotzdem wie beschrieben).

def rotate(matrix)
  result = []
  4.times { |x|
    result[x] = []
    4.times { |y|
      result[x][y] = matrix[y][3 - x]
    }
  }

  result
end

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

def print_matrix(matrix)
  4.times { |y|
    4.times { |x|
      print "#{matrix[x][y]} "
    }
    puts ""
  }
end

print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))

Das Ergebnis:

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

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

Answer 2

Hier ist eine in-space rotate Methode, von Java, nur für Quadrat. für nicht-quadratische 2d Array, müssen Sie neue Array sowieso erstellen.

private void rotateInSpace(int[][] arr) {
    int z = arr.length;
    for (int i = 0; i < z / 2; i++) {
        for (int j = 0; j < (z / 2 + z % 2); j++) {
            int x = i, y = j;
            int temp = arr[x][y];
            for (int k = 0; k < 4; k++) {
                int temptemp = arr[y][z - x - 1];
                arr[y][z - x - 1] = temp;
                temp = temptemp;

                int tempX = y;
                y = z - x - 1;
                x = tempX;
            }
        }
    }
}

Code zum Drehen eines 2d-Arrays beliebiger Größe durch Erstellen eines neuen Arrays:

private int[][] rotate(int[][] arr) {
    int width = arr[0].length;
    int depth = arr.length;
    int[][] re = new int[width][depth];
    for (int i = 0; i < depth; i++) {
        for (int j = 0; j < width; j++) {
            re[j][depth - i - 1] = arr[i][j];
        }
    }
    return re;
}

Answer 3

In Python:

import numpy as np

a = np.array(
    [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 0, 1, 2],
        [3, 4, 5, 6]
    ]
)

print(a)
print(b[::-1, :].T)

Answer 4

Implementierung von dimple's +90 Pseudocode (z.B. Transponieren und Umkehren jeder Zeile) in JavaScript:

function rotate90(a){
  // transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
  a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
  // row reverse
  for (i in a){
    a[i] = a[i].reverse();
  }
  return a;
}

Answer 5

Hier ist die Java-Version:

public static void rightRotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer;
        int last = n - 1 - first;
        for (int i = first; i < last; i++) {
           int offset = i - first;
           int temp = matrix[first][i];
           matrix[first][i] = matrix[last-offset][first];
           matrix[last-offset][first] = matrix[last][last-offset];
           matrix[last][last-offset] = matrix[i][last];
           matrix[i][last] = temp;
        }
    }
}

Bei dieser Methode wird zunächst die äußerste Schicht gedreht, dann wird die innere Schicht quadratisch angefahren.