yicong@algo: ~/code/06-matrix/0048-rotate-image.cpp

yicong@algo:~/code/06-matrix$ cat 0048-rotate-image.cpp

48. 旋转图像

中等 矩阵 题目 ↗ 源码 ↗

// 思路

先转置,然后垂直镜像 顺时针旋转 90° 拆成两步,两步都是原地交换: ① 沿主对角线转置:(i, j) ↔ (j, i) —— 只遍历上三角 ② 每一行左右翻转:(i, j) ↔ (i, n-1-j) —— 也就是沿垂直轴镜像 为什么这两步合起来正好是顺时针 90°: 顺时针的目标映射是 (i, j) → (j, n-1-i)。 先转置,元素到了 (j, i);再左右翻转把列下标 i 变成 n-1-i, 于是落到 (j, n-1-i),和目标映射完全对上。 换个搭配就是别的角度,这张表值得记住: 转置 + 左右翻转 = 顺时针 90° 转置 + 上下翻转 = 逆时针 90° 左右翻转 + 上下翻转 = 180° 直接按公式 (i,j) → (j, n-1-i) 硬搬需要另一个矩阵,O(n²) 空间; 而这个拆法全程原地交换,额外空间只有 O(1)。

// 时间复杂度

O(n²) 这里的 n 是矩阵的阶(边长),矩阵一共 n² 个元素。 两趟循环各遍历约 n²/2 个格子,每格做常数次交换,合计 O(n²)。 (不是 O(n log n)——每次操作都是 O(1),总工作量正比于元素个数。)

// 空间复杂度

O(1) 全部原地交换,只用了一个临时变量。

// 易错点

1. 转置时内层 j 必须从 i 开始,只遍历上三角。 如果写成 j = 0,每个格子会被交换两次,等于什么也没做。 2. 「转置 + 左右翻转」是顺时针,「转置 + 上下翻转」是逆时针,很容易记反。 自检方法:顺时针 90° 后,原本右上角的元素应该跑到右下角。 3. 局部变量取名 swap 会和 std::swap 撞名(上面有 using namespace std)。 这段代码里能通过编译,但一旦在同一个作用域想调 std::swap 就会报 error: 'swap' cannot be used as a function。改成 tmp 更稳妥。 4. ndiv2 里的奇偶分支是多余的,n/2 就够: 偶数时两者相同;奇数时多出来的那一轮是"中间列和自己换",无害但多余。 5. 复杂度是 O(n²) 不是 O(n log n)——n 是边长,元素总数是 n²。

// 面试口述要点

1. 先说物理映射:顺时针 90° 是 (i,j) → (j, n-1-i),硬搬需要额外矩阵,O(n²) 空间; 2. 再给拆解:转置 + 左右翻转,两步都是原地交换,时间 O(n²)、空间 O(1); 3. 主动把三种角度的组合都说清楚,说明你是真的理解了映射,而不是背公式; 4. 如果被追问"能不能一趟做完",可以给分层四点轮换: 每次同时转动同一圈的四个位置,也是一趟 O(n²)/O(1), 但下标推导更容易写错,性价比不如两趟法。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = (int)matrix.size();
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++) {
                int swap = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = swap;
            }
        int ndiv2 = (n % 2 == 0) ? n / 2 : (n + 1) / 2; 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < ndiv2; j++) {
                int swap = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = swap;
            }
    }
};

// 本地测试:先读阶数 n,再读 n*n 个元素(按行);输出顺时针旋转 90 度后的矩阵
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> matrix[i][j];

    Solution().rotate(matrix);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            cout << matrix[i][j] << (j + 1 == n ? '\n' : ' ');
    }
    return 0;
}