LeetCode 热题 100 48. 旋转图像-EW帮帮网

LeetCode 热题 100 | 48. 旋转图像

大家好，今天我们来解决一道经典的算法题——旋转图像。这道题在LeetCode上被标记为中等难度，要求我们将一个 n × n 的二维矩阵（图像）顺时针旋转90度，并且必须原地修改矩阵，不能使用额外的矩阵空间。下面我将详细讲解解题思路，并附上Python代码实现。

问题描述

给定一个 n × n 的二维矩阵 matrix，表示一个图像。请将该图像顺时针旋转90度。要求原地旋转，不能使用另一个矩阵来旋转图像。

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

解题思路

核心思想

转置 + 反转：
- 首先对矩阵进行转置（即行变列，列变行）。
- 然后对每一行进行反转，即可得到顺时针旋转90度的结果。
原地操作：
- 直接在原矩阵上进行转置和反转操作，不需要额外的空间。

Python代码实现

def rotate(matrix):
    n = len(matrix)
    
    # 转置矩阵
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    # 反转每一行
    for i in range(n):
        matrix[i].reverse()

# 测试示例
matrix1 = [[1,2,3],[4,5,6],[7,8,9]]
matrix2 = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]

rotate(matrix1)
rotate(matrix2)

print(matrix1)  # 输出: [[7,4,1],[8,5,2],[9,6,3]]
print(matrix2)  # 输出: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

代码解析

转置矩阵：
- 使用双重循环遍历矩阵的上三角部分（i 从 0 到 n-1，j 从 i 到 n-1）。
- 交换 matrix[i][j] 和 matrix[j][i]，实现转置。
反转每一行：
- 使用 reverse() 方法对每一行进行反转。
原地操作：
- 直接在原矩阵上进行转置和反转，不需要额外的空间。

复杂度分析

时间复杂度：O(n²)，其中 n 是矩阵的行数（或列数）。我们需要遍历矩阵的每一个元素进行转置和反转。
空间复杂度：O(1)，只使用了常数个额外空间。

示例运行

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

进阶：其他解法

方法一：四角旋转

def rotate_four_corners(matrix):
    n = len(matrix)
    for i in range(n // 2):
        for j in range(i, n - 1 - i):
            # 保存左上角的值
            temp = matrix[i][j]
            # 左下角 → 左上角
            matrix[i][j] = matrix[n - 1 - j][i]
            # 右下角 → 左下角
            matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
            # 右上角 → 右下角
            matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
            # 左上角 → 右上角
            matrix[j][n - 1 - i] = temp

# 测试示例
matrix1 = [[1,2,3],[4,5,6],[7,8,9]]
matrix2 = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]

rotate_four_corners(matrix1)
rotate_four_corners(matrix2)

print(matrix1)  # 输出: [[7,4,1],[8,5,2],[9,6,3]]
print(matrix2)  # 输出: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

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

总结

通过使用转置 + 反转的方法，我们可以高效地将矩阵顺时针旋转90度，并且原地修改矩阵。这种方法直观且易于实现，适合大多数场景。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！

LeetCode 热题 100 48. 旋转图像