Rotate Image

Q: Wie hoch ist die Zeit- und Platzkomplexität beim Drehen einer Matrix?

Das Drehen einer n × n -Matrix benötigt O(n²) Zeit, da nahezu jeder Wert einmal verschoben werden muss. Die Methode mit Transponieren und Umkehren benötigt O(1) zusätzlichen Speicherplatz. Das Erstellen einer gedrehten Kopie benötigt ebenfalls O(n²) Zeit, verwendet aber O(n²) zusätzlichen Speicherplatz.

MittelArrays und Strings Mathe und Simulation

+10

Du erhältst ein n × n-Raster aus Ganzzahlen, eine Liste pro Zeile. Drehe es um eine Vierteldrehung im Uhrzeigersinn und gib es zurück. Die oberste Zeile wird zur ganz rechten Spalte, die zweite Zeile zur Spalte links davon und so weiter: Der Wert an Position (i, j) landet an Position (j, n-1-i). Du darfst das Raster direkt verändern; gib es zurück.

Funktion

rotateImage(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: das quadratische Raster, eine innere Liste pro Zeile
Gibt zurückinteger-2d-array: Die Matrix wurde um 90 Grad im Uhrzeigersinn gedreht.

Einschränkungen

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Beispiele

Eingabe: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Ausgabe: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Erklärung: Die erste Zeile, 3 7 1, wird zur letzten Spalte, von oben nach unten gelesen. Die erste Spalte, 3 9 4, wird, von unten nach oben gelesen, zur ersten Zeile [4, 9, 3]. Der mittlere Wert 5 bleibt an Ort und Stelle.

Weiterführende Frage

Welche zwei Schritte an Ort und Stelle drehen die Matrix um 180 Grad, und kannst du das mit einem einzigen Durchlauf von Vertauschungen erledigen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Wohin jeder Wert gelangt, lässt sich durch eine Formel ausdrücken: (i, j) wird zu (j, n-1-i). Der schwierige Teil besteht darin, die Werte ohne eine zweite Matrix zu verschieben, denn beim Schreiben eines Werts in seine neue Zelle wird ein Wert überschrieben, der noch nicht verschoben wurde. Eine Transposition gefolgt von einer Umkehrung der Zeilen führt dieselbe Vierteldrehung mit paarweisen Vertauschungen aus.

Eine gedrehte Kopie erstellen

Idee

Zeile i wird zur Spalte n-1-i, und der Wert an Position j in der Zeile landet an Position j weiter unten in dieser Spalte, also in Zeile j. Daher gilt result[j][n-1-i] = matrix[i][j]. Im ersten Beispiel gelangt die 4 in Zeile 2, Spalte 0 zu Zeile 0, Spalte 0. Deshalb beginnt die Antwort mit 4.

Die Werte bewegen sich in Zyklen zu viert, daher würde das Schreiben an Ort und Stelle einen Wert überschreiben, bevor er weiterbewegt wird: Die 3 würde die 1 in der oberen rechten Ecke überschreiben. Die Kopie kostet n² zusätzliche Zellen, 4,900 bei n = 70.

Algorithmus

Erstelle eine n × n-Ergebnismatrix.
Kopiere für jede Zeile i und jede Spalte j matrix[i][j] nach result[j][n-1-i].
Gib das Ergebnis zurück.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Transponiere und kehre dann jede Zeile um

Idee

Eine Transponierung verschiebt (i, j) nach (j, i), und das Umkehren einer Zeile verschiebt Spalte c nach Spalte n-1-c. Zusammen verschieben sie (i, j) nach (j, n-1-i) – genau an die Position, an die es durch die Drehung gelangt.

Beide Schritte werden direkt an Ort und Stelle ausgeführt, da jeder aus einer Reihe von Paarvertauschungen besteht. Bei einer Transponierung gehören matrix[i][j] und matrix[j][i] jeweils in die Zelle des anderen, daher genügt ein Tausch für beide. Tausche nur die Paare mit j > i, sonst wird jedes Paar wieder zurückgetauscht. Beim Umkehren einer Zeile werden ihre beiden Enden vertauscht, und der Vorgang wandert nach innen.

Beim ersten Beispiel ergibt die Transponierung [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: Jede Zeile enthält nun eine frühere Spalte. Das Umkehren jeder Zeile ergibt die Antwort.

Die Transponierung führt n(n-1)/2 Vertauschungen aus und das Umkehren n·⌊n/2⌋, daher beträgt der Aufwand O(n²), mit wenigen Variablen zusätzlichem Speicher. Die R-Version kopiert die Eingabe zunächst in eine R-Matrix, daher beträgt ihr zusätzlicher Speicher O(n²).

Algorithmus

Vertausche für jede Zelle oberhalb der Hauptdiagonalen, (i, j) mit j > i, ihren Wert mit dem Wert der Zelle (j, i).
Vertausche in jeder Zeile den ersten und letzten Wert und bewege beide Enden nach innen, bis sie sich treffen.
Gib die Matrix zurück.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Stolperfallen und Grenzfälle

Transponieren mit j, das bei 0 beginnt. Jedes Paar wird zweimal vertauscht, wodurch sich das Transponieren aufhebt. Das Ergebnis sind daher nur die umgekehrten Zeilen, also ein Spiegelbild.
Vor dem Transponieren umkehren. Diese Reihenfolge dreht die Matrix gegen den Uhrzeigersinn. Ein Test mit einer 2 × 2-Matrix deckt den Fehler auf: [[1, 2], [3, 4]] muss zu [[3, 1], [4, 2]] werden.
matrix[j][n-1-i] = matrix[i][j] in dieselbe Matrix schreiben. Die Zielzelle enthält weiterhin einen Wert, der noch nicht verschoben wurde, und dieser geht verloren.
n-i statt n-1-i verwenden. Bei 0-basierten Indizes ist die letzte Spalte n-1, daher läuft n-i für i = 0 über das Ende hinaus.

Häufige Fragen3

Wie hoch ist die Zeit- und Platzkomplexität beim Drehen einer Matrix?

Das Drehen einer n × n-Matrix benötigt O(n²) Zeit, da nahezu jeder Wert einmal verschoben werden muss. Die Methode mit Transponieren und Umkehren benötigt O(1) zusätzlichen Speicherplatz. Das Erstellen einer gedrehten Kopie benötigt ebenfalls O(n²) Zeit, verwendet aber O(n²) zusätzlichen Speicherplatz.

Wie dreht man eine Matrix gegen den Uhrzeigersinn?

Tausche die Reihenfolge der beiden Schritte: Kehre zuerst jede Zeile um und transponiere dann. Du kannst auch transponieren und anschließend die Reihenfolge der Zeilen umkehren. In beiden Fällen landet der Wert an Position (i, j) bei (n-1-j, i).

Kannst du eine Matrix drehen, indem du jeweils vier Werte verschiebst?

Ja. Jeder Wert außerhalb des Zentrums gehört zu einem Zyklus aus vier Zellen: (i, j), (j, n-1-i), (n-1-i, n-1-j) und (n-1-j, i). Arbeite Ring für Ring, speichere einen Wert jedes Zyklus in einer Variablen und verschiebe die anderen drei. Das hat dieselbe Laufzeit von O(n²) und benötigt O(1) Speicherplatz, allerdings gibt es mehr Indexarithmetik, bei der man Fehler machen kann.

def rotateImage(matrix):
    # Schreibe hier den Code

Test #1

Test #2

Argument

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

Erwartete Ausgabe

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