Python-Spiralmatrix-Durchquerung
Durchlaufen und Auflisten der Elemente einer 2D-Matrix in Spiralreihenfolge in Python.
Übersicht
Das Durchlaufen einer Spiralmatrix ist ein klassisches mehrdimensionales Array-Problem. Dazu ist es erforderlich, die Außengrenzen im Uhrzeigersinn zu überqueren und die Grenzen schrittweise zu verkleinern.
Wir pflegen vier Zeiger: „oben“, „unten“, „links“ und „rechts“, um die Grenzen der nicht besuchten Matrixteile zu verfolgen.
Indem wir der Reihe nach von links nach rechts, von oben nach unten, von rechts nach links und von unten nach oben durchlaufen, decken wir systematisch alle Zellen ab.
Code- und Ausführungsausgabe
Spiraldurchlauf im Uhrzeigersinn, der die Indexmanipulation zeigt.
def spiral_order(matrix):
if not matrix:
return []
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# Traverse Right
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Traverse Down
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
if top <= bottom:
# Traverse Left
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
if left <= right:
# Traverse Up
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print("Matrix Spiral Order:")
print(spiral_order(grid))Matrix Spiral Order:
[1, 2, 3, 6, 9, 8, 7, 4, 5]Schrittweise Umsetzung
- 2D-Grafik-Rendering und Spiralpfadverfolgung
- Rasterlayout-Navigationsmuster in Daten-Engines
- Erweiterte Algorithmenbewertungstests
Häufig gestellte Fragen
Wie groß ist die zeitliche Komplexität der Spiraldurchquerung?
Die Zeitkomplexität beträgt O(m * n), wobei m für Zeilen und n für Spalten steht, da wir jede Zelle im Raster genau einmal besuchen.