Spiral Matrix

Средняя№54спираль

Дана матрица чисел, строки × столбцы. Нужно выписать все числа по спирали: по верхней строке вправо, вниз по правому столбцу, назад по нижней строке, вверх по левому столбцу, и дальше так же по кольцу внутри, пока каждое число не будет взято ровно один раз. Наш пример: 3 × 5, [1, 2, 3, 4, 5], [12, 13, 14, 15, 6], [11, 10, 9, 8, 7]. Числа идут вдоль спирали, поэтому ответ считает подряд: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].

54 Spiral MatrixРазбор · 1×

Пример: 3 × 5, ширина больше высоты: после внешнего кольца остаётся одна строка, и проверка в середине цикла не даёт прочитать её второй раз.

01234012123451213141561110987out
ещё не прочитанотолько что добавилив outбез проверки попало бы дваждыответ

Начинаем с пустого out

01/30
сначала · назад · пуск · шаг
Скорость
1function spiralOrder(m):
2 out = []
3 top, bottom = 0, rows - 1
4 left, right = 0, cols - 1
5 while top <= bottom and left <= right:
6 for c from left to right: add m[top][c]
7 top = top + 1
8 for r from top to bottom: add m[r][right]
9 right = right - 1
10 if top > bottom or left > right: break
11 for c from right down to left: add m[bottom][c]
12 bottom = bottom - 1
13 for r from bottom down to top: add m[r][left]
14 left = left + 1
15 return out
состояние
out
[]
top
–
bottom
–
left
–
right
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Четыре границы всегда обрамляют ровно непрочитанные клетки. Каждая сторона читает один край этой рамки и сдвигает свою границу внутрь на единицу, поэтому ни одна клетка не читается дважды и ни одна не пропускается.
  2. После верхней строки и правого столбца рамка может уже опустеть: оставалась одна строка или один столбец. Это ловит проверка перед нижней строкой; без неё нижней строкой стала бы та же строка, прочитанная задом наперёд.
  3. Цикл кончается, когда границы пересекаются: top проходит bottom или left проходит right. Тогда между ними ничего нет.

Сложность

Время O(строки × столбцы): каждая клетка читается один раз. Память O(1), не считая самого ответа: четыре границы.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.