Travessia da matriz espiral do Python
Percorra e liste os elementos de uma matriz 2D em ordem espiral em Python.
Visão geral
A travessia de matriz espiral é um problema clássico de array multidimensional. Requer atravessar as fronteiras externas no sentido horário e diminuir progressivamente as fronteiras.
Mantemos quatro ponteiros: `top`, `bottom`, `left` e `right` para rastrear os limites das partes da matriz não visitadas.
Percorrendo da esquerda para a direita, de cima para baixo, da direita para a esquerda e de baixo para cima em sequência, cobrimos todas as células sistematicamente.
Saída de código e execução
Percurso espiral no sentido horário mostrando a manipulação do índice.
spiral.py
Experimente no Editordef 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))Saída terminal
Matrix Spiral Order:
[1, 2, 3, 6, 9, 8, 7, 4, 5]Implementação passo a passo
- Renderização de gráficos 2D e rastreamento de caminho em espiral
- Padrões de navegação de layout de grade em mecanismos de dados
- Testes de avaliação de algoritmo avançado
Perguntas frequentes
Qual é a complexidade de tempo da travessia em espiral?
A complexidade do tempo é O(m * n), onde m são linhas en são colunas, porque visitamos cada célula da grade exatamente uma vez.