48. 旋转图像

题目链接（中等）

题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像 顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

数据范围：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

示例

示例 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]]

方法一：使用辅助数组

思路及解法

对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。用公式表示：

[
\text{matrix_new}[j][n - i - 1] = \text{matrix}[i][j]
]

遍历原矩阵的每个元素，按上述规则放入辅助数组，最后再把辅助数组的内容复制回原矩阵。

注意 Python 中不能直接 matrix = matrix_new，因为这只是重新绑定名字，原矩阵不会被修改。必须用 matrix[:] = matrix_new 原地替换内容。

代码

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        # 创建同样大小的辅助数组
        matrix_new = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                matrix_new[j][n - i - 1] = matrix[i][j]
        # 原地复制回原矩阵
        matrix[:] = matrix_new

复杂度分析

• 时间复杂度：$O(N^2)$，其中 $N$ 是矩阵边长。需要遍历所有元素。
• 空间复杂度：$O(N^2)$，使用了同样大小的辅助数组。

方法二：原地旋转（四元交换）

思路及解法

观察到旋转时四个位置构成一个循环：

[
(i, j) \rightarrow (j, n-1-i) \rightarrow (n-1-i, n-1-j) \rightarrow (n-1-j, i) \rightarrow (i, j)
]

每次可以一次性交换这四个位置的值，用一个临时变量 temp 暂存即可完成原地旋转。

需要枚举的位置：只需处理矩阵的左上角四分之一区域。

• 当 n 为偶数时，枚举 n/2 行、n/2 列；

• 当 n 为奇数时，中心点不动，枚举 n//2 行、(n+1)//2 列。

代码中直接用 for i in range(n // 2): for j in range((n + 1) // 2): 同时覆盖奇偶两种情况。

代码

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range((n + 1) // 2):
                (
                    matrix[i][j],
                    matrix[n - j - 1][i],
                    matrix[n - i - 1][n - j - 1],
                    matrix[j][n - i - 1],
                ) = (
                    matrix[n - j - 1][i],
                    matrix[n - i - 1][n - j - 1],
                    matrix[j][n - i - 1],
                    matrix[i][j],
                )

复杂度分析

• 时间复杂度：$O(N^2)$，每个元素只被访问常数次。
• 空间复杂度：$O(1)$，原地交换，只用常数个临时变量。

方法三：翻转代替旋转

思路及解法

顺时针旋转 90 度等价于：

1. 水平翻转：matrix[row][col] 与 matrix[n-1-row][col] 交换；
2. 主对角线翻转：matrix[row][col] 与 matrix[col][row] 交换。

两步合起来正好等于顺时针旋转 90 度：

[
\text{matrix}[row][col] \xrightarrow{\text{水平翻转}} \text{matrix}[n-1-row][col] \xrightarrow{\text{主对角线翻转}} \text{matrix}[col][n-1-row]
]

与方法一的关键等式一致。

代码

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)

        # 水平翻转
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]

        # 主对角线翻转
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

复杂度分析

• 时间复杂度：$O(N^2)$，两次翻转各遍历一半元素。
• 空间复杂度：$O(1)$，原地交换，只用常数个临时变量。

三种方法对比

方法	时间	空间	是否原地	特点
辅助数组	$O(N^2)$	$O(N^2)$	否	思路最简单，但需要额外空间
四元交换	$O(N^2)$	$O(1)$	是	一次交换四个位置，需理解循环关系
翻转代替旋转	$O(N^2)$	$O(1)$	是	代码最简洁，容易记忆

总结

• 方法一：用公式 matrix_new[j][n-1-i] = matrix[i][j] 直接生成结果，适合快速实现，但违反原地要求。
• 方法二：找到四个位置的循环关系，一次性交换，原地完成，是标准解法。
• 方法三：先水平翻转，再沿主对角线翻转，两步等价于旋转 90 度，代码最少，推荐面试使用。