Проблема
Имея изображение, представленное матрицей N x N, напишите метод для поворота изображения на 90 градусов.
Эта проблема требует двух шагов, чтобы найти решение.
Шаг 1
Чтобы решить эту проблему, первым шагом является транспонирование матрицы.
Транспонирование матрицы — это оператор, который переворачивает матрицу по ее диагонали; то есть он переключает индексы строки и столбца матрицы A, создавая другую матрицу, часто обозначаемую Aᵀ
Визуально это выглядит примерно так.
Эта матрица содержит четыре значения, причем значения 1
и 4
действуют как диагональ, а значения 2
и 3
затем транспонируются (меняются местами).
Элементы на диагональной линии не меняются местами, а остаются в исходном положении. Это иллюстрируется следующим образом.
Транспонированная матрица показана справа. Обратите внимание, что числа, выделенные черным цветом в правой матрице, не изменились.
Шаг 2
После транспонирования матрицы нам нужно поменять местами первый элемент с последним элементом в каждой строке (подмассиве), двигаясь внутрь, пока мы не достигнем середины. Элементы в середине не меняются местами.
Теперь код
Это имеет временную и пространственную сложность O(n2)
и O(1)
соответственно.
Вы можете получить доступ к суть Github здесь.
Удачного кодирования.