Przechodzenie przez macierz spiralną Pythona
Przemierzaj i wyświetlaj listę elementów macierzy 2D w kolejności spiralnej w Pythonie.
Przegląd
Przechodzenie przez macierz spiralną jest klasycznym problemem z tablicą wielowymiarową. Wymaga przekraczania granic zewnętrznych zgodnie z ruchem wskazówek zegara i stopniowego ich zmniejszania.
Utrzymujemy cztery wskaźniki: „góra”, „dół”, „lewy” i „prawy”, aby śledzić granice nieodwiedzonych części macierzy.
Przechodząc kolejno od lewej do prawej, od góry do dołu, od prawej do lewej i od dołu do góry, systematycznie pokrywamy wszystkie komórki.
Dane wyjściowe kodu i wykonania
Przemieszczanie się po spirali zgodnie z ruchem wskazówek zegara pokazujące manipulację indeksem.
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]Wdrażanie krok po kroku
- Renderowanie grafiki 2D i śledzenie ścieżki spiralnej
- Wzorce nawigacji układu siatki w silnikach danych
- Zaawansowane testy oceny algorytmów
Często zadawane pytania
Jaka jest złożoność czasowa przejścia spirali?
Złożoność czasowa wynosi O(m * n), gdzie m to wiersze, a n to kolumny, ponieważ każdą komórkę w siatce odwiedzamy dokładnie raz.