Traversée de la matrice spirale Python
Parcourez et répertoriez les éléments d'une matrice 2D dans l'ordre en spirale en Python.
Aperçu
Le parcours d’une matrice spirale est un problème classique de tableau multidimensionnel. Cela nécessite de traverser les frontières extérieures dans le sens des aiguilles d’une montre et de les réduire progressivement.
Nous maintenons quatre pointeurs : « top », « bottom », « left » et « right » pour suivre les limites des parties de la matrice non visitées.
En parcourant successivement de gauche à droite, de haut en bas, de droite à gauche et de bas en haut, nous couvrons systématiquement toutes les cellules.
Sortie de code et d'exécution
Traversée en spirale dans le sens des aiguilles d'une montre montrant la manipulation de l'index.
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]Mise en œuvre étape par étape
- Rendu graphique 2D et suivi du chemin en spirale
- Modèles de navigation en grille dans les moteurs de données
- Tests avancés d’évaluation d’algorithmes
Foire aux questions
Quelle est la complexité temporelle du parcours en spirale ?
La complexité temporelle est O(m * n) où m représente les lignes et n les colonnes, car nous visitons chaque cellule de la grille exactement une fois.