如何将一个 N×N 的矩阵原地旋转 90 度？

简化版

顺时针旋转 90° 有个漂亮的原地做法：先沿主对角线转置（a[i][j] 与 a[j][i] 交换），再把每一行左右翻转。两步下来就等于顺时针转了 90°，不需要额外的矩阵，空间 O(1)。

详细版

以顺时针旋转 90° 为例，规律是：原来第 i 行，会变成新的第 (n-1-i) 列。直接按这个映射搬到新矩阵当然可以，但要 O(n²) 额外空间。原地做法用「转置 + 翻转」两步：

void rotate(int[][] a) {
    int n = a.length;
    // 第一步：转置（沿主对角线交换，行列互换）
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int t = a[i][j]; a[i][j] = a[j][i]; a[j][i] = t;
        }
    // 第二步：每一行左右翻转
    for (int i = 0; i < n; i++)
        for (int l = 0, r = n - 1; l < r; l++, r--) {
            int t = a[i][l]; a[i][l] = a[i][r]; a[i][r] = t;
        }
}

顺时针 90° = 转置 + 每行左右翻转。
逆时针 90° = 转置 + 每列上下翻转（或先左右翻转再转置）。

注意转置时内层从 j = i+1 开始，避免把每个元素交换两次又换回去。

完整版教学

一、先理解旋转的坐标映射

一个 n×n 矩阵顺时针转 90°，位置 (i, j) 的元素会去哪？答案是 (j, n-1-i)。也就是：

原来的第一行（顶部）转完变成最后一列（右侧）。
原来的第一列（左侧）转完变成第一行（顶部）。

如果开一个新矩阵 b，直接令 b[j][n-1-i] = a[i][j] 就能旋转，简单但要 O(n²) 额外空间。面试的关键是**原地（in-place）**完成。

二、为什么「转置 + 翻转」等价于旋转

拆开看这两步对坐标干了什么：

转置：(i, j) → (j, i)，沿主对角线镜像。
每行左右翻转：(j, i) → (j, n-1-i)。

两步合起来：(i, j) → (j, n-1-i)，正好就是顺时针旋转 90° 的映射！所以这两个简单操作的组合，等价于旋转。妙就妙在转置和行翻转都能原地做，于是整体也就原地完成了。

三、逆时针怎么办

逆时针 90° 的映射是 (i, j) → (n-1-j, i)。对应做法：

转置 + 每列上下翻转，或者
每行先左右翻转 + 再转置。

记忆技巧：顺时针「转置后翻行」，逆时针「转置后翻列」。

四、另一种原地法：分圈四向交换

还有一种做法是把矩阵看成一圈一圈的「环」，每次取一组 4 个对应位置的元素，一次性四向轮换：

temp = 上; 上 = 左; 左 = 下; 下 = 右; 右 = temp;

从最外圈到最内圈逐圈处理。它也是 O(1) 空间，但下标计算容易写错。相比之下「转置 + 翻转」代码更短、更不易错，是面试首选。

五、复杂度与易错点

时间 O(n²)：每个元素都要被处理一次，无法更低（因为必须访问所有元素）。
空间 O(1)：原地交换，不开新矩阵。
易错点：转置内层循环必须从 j = i+1 开始（或 j < i），否则每个元素被交换两遍等于没换；翻转时左右指针相遇即停。

目标	原地步骤	坐标结果
顺时针 90°	主对角线转置 + 每行左右翻转	`(i,j) -> (j,n-1-i)`
逆时针 90°	主对角线转置 + 每列上下翻转	`(i,j) -> (n-1-j,i)`
水平翻转	每行左右交换	`(i,j) -> (i,n-1-j)`
垂直翻转	每列上下交换	`(i,j) -> (n-1-i,j)`

用 3×3 矩阵验证顺时针旋转：

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
原矩阵       转置后       每行翻转后

“原地旋转”通常默认是方阵 n*n。如果是 m*n 非方阵，旋转后形状会变成 n*m，一般不能在原矩阵空间里直接完成。

六、常见误区与追问

误区：转置一次就等于旋转 90°。 转置只是沿主对角线镜像，还需要每行翻转才是顺时针 90°。
误区：转置循环可以遍历所有 i,j。 全量遍历会把 (i,j) 和 (j,i) 交换两次，结果又换回去。
误区：非方阵也能用同样原地算法。 非方阵旋转后行列数变化，通常需要新矩阵承接结果。
追问：顺时针旋转的坐标映射是什么？ 原位置 (i,j) 会到新位置 (j,n-1-i)。
追问：为什么时间复杂度是 O(n²)？ 矩阵有 n² 个元素，旋转必须至少访问每个元素一次。
追问：还有不用转置的原地做法吗？ 可以按层做四向轮换，但下标更复杂，面试中“转置+翻转”通常更稳。

七、加强记忆

矩阵顺时针旋转 90° 的原地解法：先转置（沿主对角线行列互换）、再每行左右翻转，两步合成 (i,j)→(j,n-1-i) 正是旋转映射，空间 O(1)、时间 O(n²)。逆时针则是「转置 + 每列上下翻转」。转置内层从 i+1 开始，别把元素交换两次。

简化版

详细版