48. 旋转图像

题目链接：48. 旋转图像

题目描述

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

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

核心思考：矩阵翻转组合法

直接进行四点交换的原地旋转逻辑较为复杂且容易出错。一个更加优雅且直观的方法是通过两次简单的矩阵对称变换（翻转）来达成顺时针旋转 90 度的效果。

顺时针旋转 90 度的坐标变换规律为：matrix[row][col] 变为 matrix[col][n - 1 - row]。

我们可以将其拆解为两步：

1. 水平翻转 (Horizontal Flip)：
   将矩阵的第一行和最后一行交换，第二行和倒数第二行交换……依此类推。
   变换结果：matrix[row][col] 变为 matrix[n - 1 - row][col]。
2. 主对角线翻转 (Transpose)：
   沿主对角线进行元素交换（即矩阵转置）。
   变换结果：matrix[i][j] 与 matrix[j][i] 交换。
   最终结果：matrix[n - 1 - row][col] 经过转置变为 matrix[col][n - 1 - row]，正好满足旋转 90 度的要求。

这种方法仅需两次线性时间的基础翻转，逻辑清晰，且能保证 $O(1)$ 的额外空间。

解题思路 (Python)

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        
        # 1. 首先进行水平翻转（上下对调）
        start, end = 0, m - 1
        while start < end:
            matrix[start], matrix[end] = matrix[end], matrix[start]
            start += 1
            end -= 1
        
        # 2. 然后进行主对角线翻转（转置）
        for i in range(m):
            # 只有 j < i 时才交换，防止重复交换变回原样
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

复杂度分析

• 时间复杂度：$O(N^2)$，其中 $N$ 为矩阵的边长。水平翻转遍历了一半的行 $O(N^2/2)$，转置遍历了一半的元素 $O(N^2/2)$，总共执行了 $N^2$ 次元素交换级别操作。
• 空间复杂度：$O(1)$，全程在原矩阵上进行原地交换。