旋转图像
给定一个 n x n 的二维矩阵 matrix 表示一个图像。
请你将图像顺时针旋转 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。
请不要使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
提示：
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
解法一（转置 + 反转每一行）：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
swap(matrix[i][j], matrix[j][i]);
}
}
for (int i = 0; i < n; i++)
{
reverse(matrix[i].begin(), matrix[i].end());
}
}
};
解法二（分层四点交换）：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - 1 - i; j++)
{
int temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = temp;
}
}
}
};
核心思想
这题要求原地把一个 n x n 矩阵顺时针旋转 90 度。
如果不考虑原地限制，最直观的做法是新建一个矩阵 ans。
对于原矩阵中的位置：
(i, j)
顺时针旋转 90 度之后，它会去到新矩阵中的位置：
(j, n - 1 - i)
也就是：
ans[j][n - 1 - i] = matrix[i][j];
但是题目明确要求不能使用另一个矩阵，所以我们需要在原矩阵内部完成这个坐标变换。
这题最常用、最清晰的原地做法是：
先沿主对角线转置，再反转每一行。
这两个操作都可以在原矩阵上完成，并且合起来刚好等价于顺时针旋转 90 度。
坐标变化公式
先看顺时针旋转 90 度本身的坐标变化。
原矩阵中第 i 行第 j 列的元素：
matrix[i][j]
旋转后应该出现在：
matrix[j][n - 1 - i]
原因是：
- 原来的行号
i会变成新的列号，并且方向反过来，所以是n - 1 - i - 原来的列号
j会变成新的行号，所以是j
因此目标映射是：
(i, j) -> (j, n - 1 - i)
只要我们的原地操作能让每个元素都满足这个映射，就完成了顺时针旋转。
为什么转置后反转每一行是正确的
解法一分两步。
1. 沿主对角线转置
主对角线转置就是交换：
matrix[i][j] 和 matrix[j][i]
转置之后，元素的坐标变化是：
(i, j) -> (j, i)
例如：
1 2 3 1 4 7
4 5 6 -> 2 5 8
7 8 9 3 6 9
2. 反转每一行
反转每一行时，行号不变，列号左右翻转。
对于一个 n 列的矩阵，列号 i 会变成：
n - 1 - i
所以坐标变化是：
(row, col) -> (row, n - 1 - col)
转置之后，一个元素已经从：
(i, j)
来到了：
(j, i)
再反转它所在的这一行，坐标继续变成：
(j, n - 1 - i)
这正好就是顺时针旋转 90 度的目标位置。
因此：
(i, j) -> (j, i) -> (j, n - 1 - i)
等价于：
(i, j) -> (j, n - 1 - i)
所以“转置 + 反转每一行”可以完成顺时针旋转。
为什么转置要从 j = i + 1 开始
转置时只需要交换主对角线两侧的元素。
主对角线上的元素满足：
i == j
它们转置后仍然在原位置，不需要交换。
如果从 j = 0 开始遍历整个矩阵，会出现一个问题：
第一次交换：
swap(matrix[i][j], matrix[j][i]);
后面遍历到 (j, i) 时，又会交换回来。
所以我们只遍历主对角线右上方的元素：
for (int j = i + 1; j < n; j++)
这样每一对需要交换的元素只会被处理一次。
分层四点交换的思路
解法二不通过转置，而是直接按照旋转后的四个位置进行交换。
对于某一层中的一个位置：
(i, j)
它对应的四个位置分别是：
- 上：
(i, j) - 右：
(j, n - 1 - i) - 下：
(n - 1 - i, n - 1 - j) - 左：
(n - 1 - j, i)
顺时针旋转后：
- 左边的值会去到上边
- 上边的值会去到右边
- 右边的值会去到下边
- 下边的值会去到左边
所以代码中执行的是：
int temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = temp;
这里的 temp 保存上边位置的原值，避免在交换过程中被覆盖。
每次操作会同时完成四个位置的旋转。
外层循环处理一层一层的边框，内层循环处理当前层中的每一组四点。
正确性证明
我们证明：解法一可以将矩阵原地顺时针旋转 90 度。
结论 1：转置后，每个元素从 (i, j) 移动到 (j, i)
算法第一步沿主对角线交换：
swap(matrix[i][j], matrix[j][i]);
并且只交换 j > i 的位置。
对于任意一对非对角线位置 (i, j) 和 (j, i)，算法恰好交换一次。
因此，原来位于 (i, j) 的元素，转置后会位于 (j, i)。
对于主对角线元素，i == j，转置前后位置相同，也符合：
(i, i) -> (i, i)
所以结论 1 成立。
结论 2：反转每一行后，每个元素的列号会变成 n - 1 - col
算法第二步对每一行执行：
reverse(matrix[i].begin(), matrix[i].end());
反转一行不会改变元素的行号。
在长度为 n 的一行中，原列号为 col 的元素，反转后会出现在列号：
n - 1 - col
的位置。
所以反转每一行的坐标变化是：
(row, col) -> (row, n - 1 - col)
结论 2 成立。
结论 3：两步合起来等价于顺时针旋转 90 度
对于原矩阵中的任意元素 (i, j)：
第一步转置后，它的位置变成：
(j, i)
第二步反转每一行后，它的位置变成：
(j, n - 1 - i)
这正好是顺时针旋转 90 度的目标坐标。
也就是说，对任意元素都有：
(i, j) -> (j, n - 1 - i)
因此所有元素都会被放到旋转后的正确位置。
结论 4：算法满足原地要求
转置操作只使用若干次 swap。
反转每一行时，标准库 reverse 也是在当前行内部交换元素。
整个过程中没有创建另一个 n x n 矩阵，只使用了常数级额外变量。
所以算法满足题目的原地旋转要求。
得出结论
由结论 1 可知，第一步可以正确完成主对角线转置。
由结论 2 可知，第二步可以正确完成每一行的左右反转。
由结论 3 可知，这两个操作合起来正好等价于顺时针旋转 90 度。
由结论 4 可知，算法满足原地操作要求。
因此算法正确。
举例理解
以：
matrix = [[1,2,3],
[4,5,6],
[7,8,9]]
为例。
第一步，沿主对角线转置：
1 2 3 1 4 7
4 5 6 -> 2 5 8
7 8 9 3 6 9
第二步，反转每一行：
1 4 7 7 4 1
2 5 8 -> 8 5 2
3 6 9 9 6 3
最终结果就是：
[[7,4,1],
[8,5,2],
[9,6,3]]
再看坐标变化。
原来左上角元素 1 的位置是：
(0, 0)
旋转后位置应该是：
(0, 2)
根据公式：
(i, j) -> (j, n - 1 - i)
代入 i = 0，j = 0，n = 3：
(0, 0) -> (0, 2)
正好对应最终矩阵中的右上角。
复杂度分析
解法一
转置矩阵时，需要处理大约一半的元素。
反转每一行时，每个元素也会被处理一次。
所以总时间复杂度是：
O(n^2)
整个过程只使用常数个额外变量，没有使用额外矩阵。
所以空间复杂度是：
O(1)
解法二
分层四点交换时，每个元素也只会被移动一次。
所以时间复杂度是：
O(n^2)
只使用 temp 等常数个变量。
所以空间复杂度是：
O(1)
两种解法都满足原地旋转要求。
如果只追求代码清晰，推荐使用解法一。