Recorrido de matriz en espiral de Python
Recorre y enumera los elementos de una matriz 2D en orden espiral en Python.
Descripción general
El recorrido de una matriz en espiral es un problema clásico de matrices multidimensionales. Requiere atravesar los límites exteriores en el sentido de las agujas del reloj y reducirlos progresivamente.
Mantenemos cuatro punteros: "arriba", "abajo", "izquierda" y "derecha" para rastrear los límites de las partes de la matriz no visitadas.
Al atravesar secuencialmente de izquierda a derecha, de arriba a abajo, de derecha a izquierda y de abajo hacia arriba, cubrimos todas las celdas de forma sistemática.
Código y salida de ejecución
Recorrido en espiral en el sentido de las agujas del reloj que muestra la manipulación del índice.
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]Implementación paso a paso
- Representación de gráficos 2D y seguimiento de trayectoria en espiral
- Patrones de navegación de diseño de cuadrícula en motores de datos
- Pruebas de evaluación de algoritmos avanzados
Preguntas frecuentes
¿Cuál es la complejidad temporal del recorrido en espiral?
La complejidad del tiempo es O(m * n) donde m son filas y n son columnas, porque visitamos cada celda de la cuadrícula exactamente una vez.