Объясни поворот матрицы на 90°
Вопрос
Объясни, как повернуть квадратную матрицу на 90° по часовой стрелке на месте, и сложность решения.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Формула поворота: элемент (i, j) переходит в (j, n - 1 - i)
Разложение: транспонирование, затем разворот каждой строки
Транспонирует только при j > i, иначе вернёт исходник
O(n²) времени, O(1) доп. памяти
Знает, как повернуть против часовой
Что могут спросить следом
- Как повернуть против часовой стрелки?
- Как повернуть неквадратную матрицу?
- Как сделать поворот за один проход по слоям?
Разбор
При повороте по часовой элемент из (i, j) переезжает в (j, n - 1 - i). Делать это напрямую неудобно, поэтому раскладываю на две простые операции. Сначала транспонирую: меняю местами a[i][j] и a[j][i], но только для j > i, иначе каждую пару поменяю дважды и всё вернётся. Затем разворачиваю каждую строку. В сумме (i, j) → (j, i) → (j, n - 1 - i), то есть ровно поворот. Каждый элемент трогается константное число раз: O(n²) времени, O(1) доп. памяти. Против часовой: транспонирование и разворот порядка строк. Неквадратную на месте не повернуть, там создаю новую матрицу n × m.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.