Обход спиральной матрицы Python
Пересеките и перечислите элементы 2D-матрицы в спиральном порядке в Python.
Обзор
Обход спиральной матрицы — это классическая задача многомерного массива. Это требует пересечения внешних границ по часовой стрелке и постепенного их сужения.
Мы поддерживаем четыре указателя: «верхний», «нижний», «левый» и «правый» для отслеживания границ непосещенных частей матрицы.
Последовательно перемещаясь слева направо, сверху вниз, справа налево и снизу вверх, мы систематически охватываем все ячейки.
Код и вывод выполнения
Обход спирали по часовой стрелке, демонстрирующий манипуляции с индексами.
spiral.py
Попробуйте в редакторе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]Пошаговая реализация
- Рендеринг 2D-графики и отслеживание спирального пути
- Шаблоны навигации по сетке в механизмах обработки данных
- Тесты для оценки расширенных алгоритмов
Часто задаваемые вопросы
Какова временная сложность обхода спирали?
Временная сложность равна O(m * n), где m — строки, а n — столбцы, поскольку мы посещаем каждую ячейку сетки ровно один раз.