48. 旋转图像

给定一个 $n\times n$ 的二维矩阵 $matrix$ 表示一个图像。请你将图像顺时针旋转 $90$ 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

python">输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

python">输入：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)$ 的元素移动到 $(j,i)$，从而将矩阵的行转换为对应的列，为后续操作奠定基础；随后对转置后的矩阵逐行进行水平翻转，通过反转每一行中元素的顺序，将原本的列顺序调整为顺时针旋转后的目标位置，最终实现整个矩阵顺时针旋转 $90$ 度的效果。

算法步骤：

1. 转置矩阵：

• 遍历矩阵的上三角部分（即 $i>j$ 的情况），交换元素 matrix[i][j] 和 matrix[j][i]。
• 具体实现：
  • 外层循环 $i$ 从 $0$ 到 $n-1$（$n$ 为矩阵边长）。
  • 内层循环 $j$ 从 $0$ 到 $i-1$。
  • 每次交换 matrix[i][j] 和 matrix[j][i]。

2. 水平翻转每一行：

• 对每一行 $i$，交换其第 $j$ 个元素和第 $n-j-1$ 个元素（即行内对称位置的元素）。
• 具体实现：
  • 外层循环 i 从 0 到 n-1。
  • 内层循环 j 从 0 到 n//2 - 1（只需遍历前半部分）。
  • 每次交换 matrix[i][j] 和 matrix[i][n-j-1]。

python_30">python代码

python">class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        length = len(matrix)
        for i in range(length):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(length):
            for j in range(int(length/2)):
                tmp = matrix[i][j]
                matrix[i][j] = matrix[i][length-j-1]
                matrix[i][length-j-1] = tmp

结果

算法复杂度

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

官方题解：原地旋转

该算法通过分圈层旋转实现矩阵顺时针旋转 $90$ 度。核心思想是将矩阵视为多个同心层（从外到内逐层处理），每次直接交换同一圈层中四个对称位置的元素。具体来说，每个元素旋转后的位置可以通过坐标变换直接确定，无需借助额外空间，从而满足“原地修改”的要求。

算法步骤：

1. 分层遍历：

将矩阵分为 $n//2$ 层（例如 $n=4$ 时分 $2$ 层，$n=5$ 时分 $2$ 层，中间元素无需单独处理）。
外层循环 $i$ 遍历每一层（$i$ 的范围为 $0\le i<n//2$）。

2. 层内元素遍历：

对每一层 $i$，内层循环 $j$ 遍历该层的前 $(n+1)//2$ 个元素（例如 $n=4$ 时每层遍历 $2$ 个元素，$n=5$ 时遍历 $3$ 个元素），确保覆盖所有需要交换的位置。

3. 四元素交换：

对每个位置 $(i,j)$，找到其旋转后对应的三个对称位置：
顺时针 $90$ 度：(j, n-i-1)
顺时针 $180$ 度：$(n-i-1,n-j-1)$
顺时针 $270$ 度：$(n-j-1,i)$
将这四个位置的元素一次性交换，完成顺时针旋转 $90$ 度的目标。

4. 坐标映射公式（以位置 $(i,j)$ 为例）：

python">matrix[i][j]                 # 原始位置
matrix[n - j - 1][i]         # 顺时针 90 度后的位置
matrix[n - i - 1][n - j - 1] # 顺时针 180 度后的位置
matrix[j][n - i - 1]         # 顺时针 270 度后的位置

python_72">python代码

python">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²)
  每个元素仅被访问一次，总操作次数为矩阵元素总数 $n^2$，与遍历所有元素的时间复杂度相同。
• 空间复杂度：O(1)
  仅需常数级别的临时变量用于交换元素，无额外空间占用。

进阶版：旋转任意角度

本算法通过几何坐标变换实现矩阵（或图像）的任意角度旋转，核心思想是利用旋转矩阵对每个元素的坐标进行数学变换，将原始矩阵中的元素映射到旋转后的新位置。具体步骤如下：

• 旋转中心定位： 以矩阵中心为旋转原点，确保旋转对称性。
• 坐标变换： 对每个元素计算其相对于中心的坐标，通过旋转矩阵计算新坐标。
• 前向映射填充： 将原矩阵中元素的值填充到旋转后的坐标位置，处理可能的越界问题。

算法步骤

• 初始化参数：

  • 获取矩阵边长 $n$，计算旋转角度的弧度值 angle_radians。
  • 确定旋转中心 $center$ 为矩阵几何中心 $(n//2,n//2)$。

• 生成旋转矩阵：

  • 根据旋转弧度构造二维旋转矩阵：
    
    其中 $\theta$ 为旋转弧度。

• 创建目标矩阵：

  • 初始化一个与原始矩阵大小相同的全零矩阵 rotated_matrix，用于存放旋转结果。

• 遍历原始矩阵元素：
  对每个位置 $(i,j)$计算相对坐标：将绝对坐标转换为以旋转中心为原点的相对坐标：
  $$x=i-center[0],y=j-center[1]$$

• 应用旋转变换：
  通过矩阵乘法计算旋转后的新坐标：
  

• 还原为绝对坐标：

python">new_x_abs = round(new_x+center[0])
new_y_abs = round(new_y+center[1])

• 填充目标矩阵：
  检查新坐标 (new_x_abs, new_y_abs) 是否在矩阵范围内（0 ≤ new_x_abs < n 且 0 ≤ new_y_abs < n）。
  若合法，则将原始矩阵中 (i, j) 的值赋给目标矩阵的 (new_x_abs, new_y_abs) 位置。
• 返回结果：
  返回填充后的 rotated_matrix。

python_123">python代码

python">def rotate_matrix(matrix, angle_degrees):
    # 获取矩阵的大小
    n = matrix.shape[0]
    
    # 计算旋转角度的弧度值
    angle_radians = math.radians(angle_degrees)
    
    # 获取旋转中心
    center = (n // 2, n // 2)
    
    # 生成旋转矩阵
    rotation_matrix = np.array([[math.cos(angle_radians), -math.sin(angle_radians)],
                                [math.sin(angle_radians), math.cos(angle_radians)]])
    
    # 创建一个新的矩阵存放旋转后的结果
    rotated_matrix = np.zeros_like(matrix)
    
    # 遍历每个元素
    for i in range(n):
        for j in range(n):
            # 计算当前元素的相对中心坐标
            x, y = i - center[0], j - center[1]
            
            # 旋转坐标
            new_x, new_y = np.dot(rotation_matrix, np.array([x, y]))
            
            # 将旋转后的坐标映射回新矩阵中，取整并保持在矩阵范围内
            new_x, new_y = round(new_x + center[0]), round(new_y + center[1])
            
            # 确保新坐标仍然在矩阵范围内
            if 0 <= new_x < n and 0 <= new_y < n:
                rotated_matrix[new_x, new_y] = matrix[i, j]
    
    return rotated_matrix

关键说明

• 前向映射的局限性：
  直接通过 round 取整可能导致多个原始元素映射到同一目标位置（覆盖问题），或某些目标位置无映射（空洞问题）。
  若需更精确的结果，可采用反向映射（遍历目标矩阵，通过逆变换计算对应的原始坐标）并结合插值算法（如双线性插值）。

复杂度分析：

• 时间复杂度：O(n²)， 需遍历所有元素。
• 空间复杂度：O(n²)， 需额外存储目标矩阵。
• 适用场景：
  适用于任意角度旋转，但需权衡精度与效率。对于非 90° 倍数的旋转，建议结合插值方法优化结果。