0048. Rotate Image
==================
题目信息
--------
:题号: 0048. 旋转图像
:难度: Medium
:主题: 矩阵、坐标映射、原地置换
:原题: `LeetCode 0048 `_
:重点: 从额外矩阵按目标坐标写入,推导到四元环轮换与转置后水平翻转
题目重述
--------
给定一个 ``n x n`` 整数方阵 ``matrix``,把整幅图像顺时针旋转 ``90`` 度。
必须直接修改原矩阵,不能再分配另一个 ``n x n`` 矩阵保存旋转结果。
自建示例
--------
.. code-block:: text
输入:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9,10,11,12]
[13,14,15,16]
修改后:
[13, 9, 5,1]
[14,10, 6,2]
[15,11, 7,3]
[16,12, 8,4]
原矩阵第一列从下到上成为结果第一行,第二列从下到上成为结果第二行。
边界情况:
* ``[[7]]`` 旋转后仍为 ``[[7]]``;
* ``[[1,2],[3,4]]`` 旋转后为 ``[[3,1],[4,2]]``;
* 奇数阶矩阵的中心元素不移动。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
void copyByCoordinateMapping(std::vector>& matrix) {
const int n = static_cast(matrix.size());
std::vector> rotated(n, std::vector(n));
for (int row = 0; row < n; ++row) {
for (int col = 0; col < n; ++col) {
rotated[col][n - 1 - row] = matrix[row][col];
}
}
matrix = std::move(rotated);
}
void rotateFourWayCycles(std::vector>& matrix) {
const int n = static_cast(matrix.size());
for (int layer = 0; layer < n / 2; ++layer) {
const int last = n - 1 - layer;
for (int offset = 0; offset < last - layer; ++offset) {
const int top = matrix[layer][layer + offset];
matrix[layer][layer + offset] =
matrix[last - offset][layer];
matrix[last - offset][layer] =
matrix[last][last - offset];
matrix[last][last - offset] =
matrix[layer + offset][last];
matrix[layer + offset][last] = top;
}
}
}
void transposeThenReverseRows(std::vector>& matrix) {
const int n = static_cast(matrix.size());
for (int row = 0; row < n; ++row) {
for (int col = row + 1; col < n; ++col) {
std::swap(matrix[row][col], matrix[col][row]);
}
}
for (auto& row : matrix) {
std::reverse(row.begin(), row.end());
}
}
public:
void rotate(std::vector>& matrix) {
transposeThenReverseRows(matrix);
}
};
题解
----
目标坐标映射
~~~~~~~~~~~~
设原坐标为 ``(row, col)``。顺时针旋转后,原列号成为新行号,原行号从上到下的顺序变为新列从右到左的顺序:
.. math::
(row,col) \longrightarrow (col,n-1-row)
``copyByCoordinateMapping`` 按这个公式把每个元素写入新矩阵。映射中的两个坐标都唯一确定,因此每个原位置恰好进入
一个目标位置,不同原位置也不会冲突。该方法直接实现定义,时间为 ``O(n^2)``,问题是额外矩阵占用
``O(n^2)`` 空间。
原地写入不能逐格执行同一赋值。目标位置可能仍保存着尚未搬走的旧值,单向覆盖会破坏后续读取。需要把坐标置换中的
整组相关位置同时轮换,或把目标映射分解成只使用交换的简单变换。
四元环轮换
~~~~~~~~~~
连续四次应用旋转映射会回到起点:
.. code-block:: text
(row, col)
-> (col, n-1-row)
-> (n-1-row, n-1-col)
-> (n-1-col, row)
-> (row, col)
除奇数阶矩阵中心点外,每个位置都属于一个长度为四的环。对于第 ``layer`` 层上边的一点,四个位置为:
.. code-block:: text
top = (layer, layer + offset)
right = (layer + offset, last)
bottom = (last, last - offset)
left = (last - offset, layer)
顺时针旋转要求 ``left -> top -> right -> bottom -> left``。保存 ``top`` 的旧值后依次赋值,四个元素便能在不丢失
数据的情况下完成一次轮换。
四元环不变量
~~~~~~~~~~~~
进入第 ``layer`` 层时,外侧各层已经完成旋转,当前层及其内侧仍保持原始相对关系。只把当前层上边的前
``last - layer`` 个位置作为环代表:
.. code-block:: text
offset = 0, 1, ..., last - layer - 1
右上角不再单独作为代表,因为它已经属于 ``offset = 0`` 的环。当前层的每个非角点和角点都恰好出现在一个四元环
中;轮换结束后,整层满足目标坐标映射,内层未被修改。
外层循环只处理 ``n / 2`` 层。偶数阶矩阵的所有位置都落入某一层,奇数阶矩阵中心点单独形成长度为一的环,旋转后
仍在原处。由此所有元素恰好移动一次。
复合变换
~~~~~~~~
另一种原地路线是把旋转拆成两个简单置换。
沿主对角线转置:
.. code-block:: text
(row, col) -> (col, row)
再水平翻转每一行:
.. code-block:: text
(col, row) -> (col, n - 1 - row)
两步复合后正好得到顺时针旋转坐标:
.. code-block:: text
(row, col) -> (col, n - 1 - row)
对三阶矩阵:
.. code-block:: text
原矩阵 主对角线转置后 每行反转后
1 2 3 1 4 7 7 4 1
4 5 6 -> 2 5 8 -> 8 5 2
7 8 9 3 6 9 9 6 3
复合变换不变量
~~~~~~~~~~~~~~
转置阶段只遍历 ``col > row`` 的位置,并交换 ``matrix[row][col]`` 与 ``matrix[col][row]``。主对角线元素无需移动,
每对非对角线元素只交换一次;若遍历整个矩阵,同一对位置会被交换两次而恢复原状。
行翻转阶段在每一行内对称交换左右元素。两个阶段都只由两两交换组成,不会覆盖尚未保存的旧值;它们也都是矩阵位置
上的双射,不会遗漏或复制元素。复合坐标已经等于目标映射,因此最终矩阵就是顺时针旋转结果。
代码演进
~~~~~~~~
``copyByCoordinateMapping`` 直接按目标坐标写入新矩阵,建立最清晰的正确基线。
``rotateFourWayCycles`` 把旋转置换拆成互不重叠的四元环,每个环只用一个临时变量原地轮换。
``transposeThenReverseRows`` 将同一坐标映射分解为转置和行翻转,代码更短,公开入口采用该方法。
复杂度分析
~~~~~~~~~~
矩阵共有 ``n^2`` 个元素,三种方法都需要处理同阶数量的位置,时间复杂度均为 ``O(n^2)``。
额外矩阵方法使用 ``O(n^2)`` 空间。四元环和转置加行翻转只使用少量临时变量,额外空间为 ``O(1)``。