Rotate Image

Средняя№48поворот

Дана квадратная матрица n × n — картинка. Нужно повернуть её на 90° по часовой стрелке на месте: менять саму матрицу, без второй. Наш пример: буквы ABCD EFGH IJKL MNOP, по строкам. После поворота: MIEA NJFB OKGC PLHD — левый столбец, прочитанный снизу вверх, стал верхней строкой.

48 Rotate ImageРазбор · 1×

Пример: буквы от A до P, 4 × 4: два кольца, три цикла по четыре клетки на внешнем и один на внутреннем. На каждом шаге подсвечены клетка, откуда берём букву, и клетка, куда её пишем.

01230123ABCDEFGHIJKLMNOPtmp
ещё не двигалив этом цикле из четырёхоткуда берёмкуда записалина своём месте

n = 4. Поворот по часовой стрелке отправляет клетку (r, c) в (c, 3 - r): верхняя строка становится правым столбцом

01/30
сначала · назад · пуск · шаг
Скорость
1function rotate(m):
2 n = len(m)
3 for layer from 0 to n / 2 - 1:
4 last = n - 1 - layer
5 for i from layer to last - 1:
6 tmp = m[layer][i] // top
7 m[layer][i] = m[n - 1 - i][layer]
8 m[n - 1 - i][layer] = m[last][n - 1 - i]
9 m[last][n - 1 - i] = m[i][last]
10 m[i][last] = tmp
11 return m
состояние
n
4
layer
–
last
–
i
–
tmp
–
историянажмите шаг, чтобы вернуться

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

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

  1. Четверть оборота отправляет клетку (r, c) в (c, n - 1 - r). Четыре раза подряд — и клетка вернулась, поэтому клетки разбиваются на циклы по четыре: по одной на каждой стороне одного кольца, на одном расстоянии от угла.
  2. В цикле каждая клетка берёт значение предыдущей, поэтому отложить нужно только первое перезаписанное: tmp держит верхнюю клетку, пока её не заберёт правая.
  3. i идёт от layer до last - 1, а не до last: угол в конце стороны — это начало следующей стороны, и он уже сдвинулся в первом цикле. Ещё один шаг повернул бы его обратно.

Сложность

Время O(n²): каждая клетка переставляется один раз. Память O(1): одна запасная переменная tmp, второй матрицы нет.

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

Решить на LeetCode ↗

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