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)$，全程在原矩阵上进行原地交换。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

import sys

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]

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.rotate(matrix)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py