Rotate Image

Q: Какова временная и пространственная сложность поворота матрицы?

Поворот матрицы n × n занимает время O(n²), поскольку почти каждое значение нужно переместить один раз. Метод транспонирования и обращения требует O(1) дополнительной памяти. Создание повернутой копии также занимает время O(n²), но требует O(n²) дополнительной памяти.

СреднеМассивы и строки Математика и моделирование

+10

Вам дана сетка целых чисел размером n × n, представленная списком для каждой строки. Поверните её на четверть оборота по часовой стрелке и верните. Верхняя строка станет самым правым столбцом, вторая строка — столбцом слева от него, и так далее: значение в позиции (i, j) окажется в позиции (j, n-1-i). Вы можете изменить сетку на месте; верните её.

Функция

rotateImage(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: квадратная сетка, по одному внутреннему списку на строку
Возвращаетinteger-2d-array: матрица повернулась на 90 градусов по часовой стрелке

Ограничения

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Примеры

Ввод: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Вывод: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Пояснение: Первая строка, 3 7 1, становится последним столбцом, читаемым сверху вниз. Первый столбец, 3 9 4, читаемый снизу вверх, становится первой строкой [4, 9, 3]. Центральное значение 5 остаётся на месте.

Дополнительный вопрос

Какие два шага на месте поворачивают матрицу на 180 градусов и можно ли выполнить это за один проход обменов?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Куда перемещается каждое значение, задаёт формула: (i, j) перемещается в (j, n-1-i). Самое сложное — переместить значения без второй матрицы, потому что запись значения в новую ячейку перезаписывает значение, которое ещё не переместили. Транспонирование с последующим разворотом строк выполняет тот же поворот на четверть оборота с помощью попарных обменов.

Создайте повёрнутую копию

Идея

Строка i становится столбцом n-1-i, а значение в позиции j в строке попадает в позицию j вниз по этому столбцу, то есть в строку j. Поэтому result[j][n-1-i] = matrix[i][j]. В первом примере 4 из строки 2, столбца 0 перемещается в строку 0, столбец 0, поэтому ответ начинается с 4.

Значения перемещаются по циклам из четырёх элементов, поэтому запись на месте стерла бы значение до того, как оно переместится: 3 перезаписала бы 1 в правом верхнем углу. Копирование требует дополнительных n² ячеек — 4,900 при n = 70.

Алгоритм

Создай результирующую матрицу размером n × n.
Для каждой строки i и каждого столбца j скопируй matrix[i][j] в result[j][n-1-i].
Верни результат.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Транспонируй, затем разверни каждую строку

Идея

Транспонирование перемещает (i, j) в (j, i), а обращение строки перемещает столбец c в столбец n-1-c. Вместе эти операции перемещают (i, j) в (j, n-1-i) — именно туда, куда его помещает поворот.

Обе операции выполняются на месте, поскольку каждая представляет собой набор обменов пар элементов. При транспонировании matrix[i][j] и matrix[j][i] должны оказаться в ячейках друг друга, поэтому одного обмена достаточно, чтобы переместить оба элемента. Обменивайте только пары, для которых j > i, иначе каждый обмен будет отменён обратным. При обращении строки меняются местами её крайние элементы, затем процесс продолжается по направлению к середине.

В первом примере после транспонирования получается [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: теперь каждая строка содержит бывший столбец. Обращение каждой строки даёт ответ.

Транспонирование выполняет n(n-1)/2 обменов, а обращение строк — n·⌊n/2⌋, поэтому трудоёмкость составляет O(n²), а дополнительная память — несколько переменных. Версия на R сначала копирует входные данные в матрицу R, поэтому для неё дополнительная память составляет O(n²).

Алгоритм

Для каждой ячейки выше главной диагонали, (i, j) при j > i, поменяй её значение местами со значением ячейки (j, i).
В каждой строке поменяй местами первое и последнее значения и перемещайся от обоих концов к середине, пока они не встретятся.
Верни матрицу.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Ловушки и крайние случаи

Транспонирование, когда j начинается с 0. Каждая пара меняется местами дважды, что отменяет транспонирование, поэтому в результате строки просто перевёрнуты — получается зеркальное отражение.
Сначала перевернуть, а потом транспонировать. Такой порядок поворачивает матрицу против часовой стрелки. Проверка на матрице 2 × 2 выявит ошибку: [[1, 2], [3, 4]] должна превратиться в [[3, 1], [4, 2]].
Запись matrix[j][n-1-i] = matrix[i][j] в ту же матрицу. Целевая ячейка всё ещё содержит значение, которое не переместили, и оно теряется.
Использование n-i вместо n-1-i. При индексации с 0 индекс последнего столбца — n-1, поэтому при i = 0 значение n-i выходит за границы.

Частые вопросы3

Какова временная и пространственная сложность поворота матрицы?

Поворот матрицы n × n занимает время O(n²), поскольку почти каждое значение нужно переместить один раз. Метод транспонирования и обращения требует O(1) дополнительной памяти. Создание повернутой копии также занимает время O(n²), но требует O(n²) дополнительной памяти.

Как повернуть матрицу против часовой стрелки?

Поменяйте порядок двух шагов: сначала разверните каждую строку, затем транспонируйте матрицу. Можно также сначала транспонировать матрицу, а затем развернуть порядок строк. В любом случае значение в (i, j) окажется в (n-1-j, i).

Можешь ли ты повернуть матрицу, перемещая за раз по четыре значения?

Да. Каждое значение вне центра принадлежит циклу из четырёх ячеек: (i, j), (j, n-1-i), (n-1-i, n-1-j) и (n-1-j, i). Проходя кольцо за кольцом, сохраните в переменной одно значение из каждого цикла и сдвиньте остальные три. Временная сложность и объём дополнительной памяти остаются O(n²) и O(1), но нужно выполнить больше арифметических операций с индексами, в которых можно ошибиться.

def rotateImage(matrix):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]

Ожидаемый вывод

[[4, 9, 3], [8, 5, 7], [6, 2, 1]]