LeetCode 48. 旋转图像

◎

本节目标

把顺时针旋转拆为主对角线转置和逐行翻转，原地完成坐标变换。

这道题是矩阵解题框架中的坐标变换母题。与其直接推导四个位置的循环交换，不如把旋转拆成两个容易验证的基本操作。

查看原题

题意与约束

给定一个 n × n 方阵，将图像顺时针旋转 90°。必须直接修改输入矩阵，不能另建同规模矩阵。

从坐标映射出发

原位置 (row, col) 顺时针旋转后到达 (col, n - 1 - row)。

一次完成这个映射需要谨慎安排交换顺序。更稳定的分解是：

1. 沿主对角线转置：(row, col) → (col, row)；
2. 反转每一行：(col, row) → (col, n - 1 - row)。

组合后的坐标正好等于顺时针旋转目标。

转置时只交换主对角线一侧，即 col > row 的位置；若扫描整个矩阵，每对元素会交换两次，最终回到原处。

原地修改

函数没有返回值。它先在原矩阵中完成转置，再原地反转每一行；“转置”后的同一个矩阵继续承担第二阶段输入，因此调用者执行后直接读取原矩阵。

代码实现

C++ 使用 swap 与 reverse，Python 使用元组交换与列表 reverse，两者执行完全相同的几何分解。

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = static_cast<int>(matrix.size());
        for (int row = 0; row < n; row++) {
            for (int col = row + 1; col < n; col++) {
                swap(matrix[row][col], matrix[col][row]);
            }
        }
        for (vector<int>& row : matrix) {
            reverse(row.begin(), row.end());
        }
    }
};

Python

Python 3

class Solution:
    def rotate(self, matrix):
        n = len(matrix)
        for row in range(n):
            for col in range(row + 1, n):
                matrix[row][col], matrix[col][row] = (
                    matrix[col][row],
                    matrix[row][col],
                )
        for row in matrix:
            row.reverse()

复杂度分析

• 时间复杂度：O(n²)，转置与翻转都线性访问矩阵元素。
• 空间复杂度：O(1)，交换直接发生在原矩阵中。

易错点

• 只转置没有翻转，得到关于主对角线的镜像。
• 转置时扫描整个矩阵，使每对元素交换两次。
• 反转每一列而非每一行，得到另一个方向的旋转。
• 创建同规模结果矩阵，违反原地要求。

模式迁移

矩阵的旋转与镜像通常可以拆成转置和行列翻转的组合。遇到其他角度或方向时，先写出坐标映射，再寻找能组合出该映射的基本操作，比背诵四点交换模板更可靠。