Attraversamento della matrice a spirale di Python
Attraversa ed elenca gli elementi di una matrice 2D in ordine a spirale in Python.
Panoramica
L'attraversamento della matrice a spirale è un classico problema di array multidimensionale. Richiede l'attraversamento dei confini esterni in senso orario e la progressiva riduzione dei confini.
Manteniamo quattro puntatori: `top`, `bottom`, `left` e `right` per tracciare i limiti delle parti della matrice non visitate.
Attraversando in sequenza da sinistra a destra, dall'alto verso il basso, da destra a sinistra e dal basso verso l'alto, copriamo sistematicamente tutte le celle.
Codice e output di esecuzione
Attraversamento a spirale in senso orario che mostra la manipolazione dell'indice.
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]Implementazione passo dopo passo
- Rendering grafico 2D e tracciamento del percorso a spirale
- Modelli di navigazione del layout della griglia nei motori di dati
- Test avanzati di valutazione degli algoritmi
Domande frequenti
Qual è la complessità temporale dell'attraversamento della spirale?
La complessità temporale è O(m * n) dove m sono le righe e n le colonne, perché visitiamo ogni cella della griglia esattamente una volta.