Spiral Matrix

MittelMathe und Simulation Arrays und Strings

+10

Du erhältst eine Matrix aus Ganzzahlen mit m Zeilen und n Spalten, die als Liste von Zeilen angegeben ist. Gib alle ihre Werte in Spiralreihenfolge zurück.

Beginne in der oberen linken Ecke und gehe nach rechts entlang der obersten Zeile, dann nach unten entlang der rechten Spalte, nach links entlang der untersten Zeile und nach oben entlang der linken Spalte. Fahre im Uhrzeigersinn spiralförmig nach innen fort, bis jeder Wert genau einmal gelesen wurde.

Funktion

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

matrixinteger-2d-array: das Raster aus Ganzzahlen als Liste gleich langer Zeilen
Gibt zurückinteger-array: jeden Wert der Matrix in spiralförmiger Reihenfolge im Uhrzeigersinn, beginnend an der oberen linken Ecke

Einschränkungen

1 ≤ m, n ≤ 80, wobei m = matrix.length und n = matrix[i].length
Jede Zeile hat dieselbe Länge n.
-100 ≤ matrix[i][j] ≤ 100

Beispiele

Eingabe: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Ausgabe: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Erklärung: Die Werte zählen entlang der Spirale hoch. Der äußere Ring zeigt oben 1, 2, 3, rechts nach unten 4, 5, 6, unten zurück 7, 8 und links nach oben 9, 10. Die innere Schicht ist eine einzelne Spalte, die einmal von oben nach unten gelesen wird: 11, 12.

Eingabe: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Ausgabe: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Erklärung: Der äußere Ring ergibt 7, 1, 5, 3, dann 6, -1 an der rechten Seite nach unten, 4, 0, 8 entlang der Unterseite zurück und 2 links nach oben. Übrig bleibt die einzelne Zeile 9, -4, die einmal von links nach rechts gelesen wird.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du die Werte stattdessen gegen den Uhrzeigersinn zurückgeben, beginnend in der oberen linken Ecke und zuerst die linke Spalte nach unten durchgehend?

Tipps

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

0 von 3 geöffnet

Lösung

Hier gibt es keine raffinierte Mathematik; das Problem ist die Buchführung, und genau dabei gehen Lösungen schief. Jede Ecke muss einmal gelesen werden, nicht zweimal, und die innerste Schicht kann aus einer einzelnen Zeile oder einer einzelnen Spalte bestehen, sodass ein vollständiger Umlauf dieselben Werte erneut durchlaufen würde. Du kannst wie ein Roboter laufen, der immer dann nach rechts abbiegt, wenn er blockiert ist, und sich merkt, welche Zellen er gelesen hat. Oder du kannst die Matrix Ring für Ring mit vier schrumpfenden Grenzen abtragen, wofür kein zusätzlicher Speicher nötig ist.

Gehe und biege nach rechts ab, wenn der Weg blockiert ist

Idee

Stell dir eine Figur vor, die sich auf der Zelle oben links befindet und nach rechts schaut. Sie liest die Zelle, auf der sie steht, und versucht dann, einen Schritt nach vorn zu machen. Würde sie durch diesen Schritt die Matrix verlassen oder auf einer Zelle landen, die sie bereits gelesen hat, dreht sie sich nach rechts (rechts, unten, links, oben und dann wieder nach rechts) und macht stattdessen einen Schritt in diese Richtung. Diese Regel zeichnet die Spirale: Die Ränder der Matrix stoppen die erste Runde, und die bereits gelesenen Zellen wirken bei jeder weiteren Runde als Wände.

Speichere die Richtung als Index d in zwei kleinen Arrays, dr = [0, 1, 0, -1] und dc = [1, 0, -1, 0], sodass eine Rechtsdrehung d = (d+1) % 4 ist. Verwende ein boolesches Raster seen mit den Abmessungen der Matrix. Im ersten Beispiel liest die Figur 1, 2, 3, erreicht den rechten Rand und dreht sich nach unten für 4, 5, 6, nach links für 7, 8 und nach oben für 9, 10. Über 10 befindet sich die 1, die bereits gelesen wurde, also dreht sie sich nach rechts zu 11. Rechts von 11 befindet sich die 4, die schon gelesen wurde, also dreht sie sich nach unten zu 12.

Führe die Schleife genau m × n Mal aus, einmal pro Zelle, und du musst das Ende nie erkennen. Nach dem letzten Lesevorgang kann die Figur auf eine Wand zeigen, aber sie macht keinen weiteren Schritt. Jede Zelle wird einmal gelesen, daher beträgt die Laufzeit O(m × n). Das Raster seen benötigt zusätzlichen Speicherplatz von O(m × n), den der nächste Ansatz einspart.

Algorithmus

Starte in Zeile 0, Spalte 0, nach rechts blickend, mit einem seen-Raster, das überall auf false gesetzt ist.
Wiederhole m × n Mal: Füge den aktuellen Wert hinzu und markiere seine Zelle als gesehen.
Berechne die nächste Zelle in der aktuellen Richtung. Wenn sie außerhalb der Matrix liegt oder bereits gesehen wurde, biege nach rechts ab und berechne sie erneut.
Gehe zu dieser Zelle.
Gib die Werte in der Reihenfolge zurück, in der du sie hinzugefügt hast.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

Schäle die Schichten mit vier Grenzen ab

Idee

Die Spirale besteht aus ineinander verschachtelten Ringen. Beschreibe den aktuellen Ring mit vier Grenzen: Zeilen von top bis bottom, Spalten von left bis right. Ein Umlauf liest die oberste Zeile von left bis right, die rechte Spalte von top+1 abwärts bis bottom, die unterste Zeile von right-1 zurück bis left und die linke Spalte von bottom-1 aufwärts bis top+1. Jede Seite beginnt eine Zelle hinter dem Ende der vorherigen Seite, sodass jede Ecke genau einmal gelesen wird. Verschiebe dann alle vier Grenzen um einen Schritt nach innen und wiederhole den Vorgang, solange top ≤ bottom und left ≤ right.

Die Falle ist ein Ring, der nur eine Zeile oder eine Spalte dick ist und bei dem der Rückweg über bereits gelesene Zellen führt. Im zweiten Beispiel lauten die Grenzen nach dem äußeren Ring top = bottom = 1, left = 1 und right = 2: die einzelne Zeile 9, -4. Die oberste Zeile liest beide Werte, und die rechte Spalte hat unterhalb von top keine Zellen. Die unterste Zeile ist jedoch dieselbe Zeile, und wenn man sie zurückliefe, würde man 9 ein zweites Mal addieren. Laufe daher die unterste Zeile und die linke Spalte nur ab, wenn top < bottom und left < right. Das dritte Beispiel ist der Spiegelbildfall: In der einzelnen Spalte 4, 1, 7 würde man beim Zurücklaufen nach oben in der linken Spalte die 1 erneut lesen.

Jeder Wert wird einmal gelesen, daher beträgt die Laufzeit O(m × n), was das Minimum ist, da das Ergebnis jeden Wert enthält. Zusätzlich zum Ergebnis beträgt der Speicherbedarf vier Ganzzahlen.

Algorithmus

Setze top = 0, bottom = m-1, left = 0, right = n-1.
Lies, solange top ≤ bottom und left ≤ right gelten, die oberste Zeile von left bis right und die rechte Spalte von top+1 bis bottom.
Falls top < bottom und left < right gelten, lies die unterste Zeile von right-1 bis left und die linke Spalte von bottom-1 bis top+1.
Erhöhe top und left um eins und verringere bottom und right um eins.
Gib die Werte in der Reihenfolge zurück, in der du sie gelesen hast.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

Stolperfallen und Grenzfälle

Die Schleifen sind kurz, daher stecken die Fehler in den Ecken und in der letzten Ebene.

Die letzte Ebene wird zweimal gelesen, wenn sie aus einer Zeile oder einer Spalte besteht. Ohne die Prüfung top < bottom und left < right endet das zweite Beispiel mit 9, -4, 9, und das dritte liest 4, 1, 7, 1.
Eine Ecke wird zweimal gelesen. Wenn jede Seite von ihrer eigenen ersten bis zu ihrer eigenen letzten Zelle verläuft, wird jede Ecke von zwei Seiten gelesen. Beginne jede Seite eine Zelle nach dem Ende der vorherigen Seite.
Die Schleife läuft, solange top < bottom gilt, statt solange top ≤ bottom gilt. Dadurch wird vor der Mitte eines ungeraden Quadrats abgebrochen: In einer 3 × 3-Matrix wird der mittlere Wert nie gelesen.
Zeilen und Spalten werden bei einer nicht quadratischen Matrix verwechselt. matrix.length für beide Grenzen zu verwenden, funktioniert bei jedem quadratischen Test und schlägt bei einem 3 × 4-Test fehl.
Die dünnen Eingaben werden vergessen: eine Zeile, eine Spalte, eine Zelle. Jede davon ist eine einzelne Ebene, die nie die unterste Zeile oder die linke Spalte erreicht.
In R zählt a:b abwärts, wenn a > b gilt. Ein leerer Bereich wie 3:2 ergibt daher 3, 2 statt nichts; sichere ihn ab oder verwende seq_len. In Lua und R beginnen Zeilen und Spalten bei 1.

Häufige Fragen4

Wie hoch sind die Zeit- und Speicherkomplexität von Spiral Matrix?

Beide Ansätze lesen jeden Wert einmal, daher beträgt die Laufzeit O(m × n), und keine Lösung kann besser sein, da die Antwort jeden Wert enthält. Das schichtweise Abtragen mit vier Grenzen benötigt zusätzlich zur Antwort O(1) Speicher. Der Weg, bei dem man beim Blockiertwerden abbiegt, verwendet ein O(m × n)-Raster, um sich zu merken, welche Zellen bereits gelesen wurden.

Wie vermeidest du, bei einer Spiraltraversierung einen Wert zweimal zu lesen?

Zwei Stellen verursachen Wiederholungen. An den Ecken beginnst du jede Seite eine Zelle nach dem Ende der vorherigen Seite, sodass jede Ecke nur zu einer Seite gehört. In der letzten Ebene liest du die unterste Zeile und die linke Spalte nur dann, wenn die Ebene mehr als eine Zeile und mehr als eine Spalte hat, da der Rückweg sonst über Zellen führt, die du bereits gelesen hast.

Wie füllst du eine Matrix spiralförmig, statt sie auszulesen?

Verwende dieselben vier Grenzen und dieselben vier Seiten, aber schreibe statt zu lesen. Führe einen Zähler, der bei 1 beginnt, und speichere ihn beim Durchlaufen in jeder Zelle; erhöhe ihn jedes Mal um eins. Bei einer n × n-Matrix endet der Zähler bei n², und das erste Beispiel oben zeigt das Ergebnis für ein 4 × 3-Raster.

Warum entsteht eine Spirale, wenn man bei einer Blockade nach rechts abbiegt?

Auf der ersten Runde biegt der Läufer an den vier Rändern der Matrix ab. Bei jeder weiteren Runde dienen die zuvor gelesenen Zellen als Wände, sodass jede Runde eine Zelle vor dem Ring abbiegt, den sie beim letzten Mal durchlaufen hat. Dadurch bleibt jede Runde innerhalb der vorherigen – so entsteht die Spirale. Der Läufer muss nie wissen, in welcher Schicht er sich befindet, sondern nur, ob die nächste Zelle frei ist.

Python

def spiralOrder(matrix):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

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