当前位置：首页 > news >正文

LeetCode 热题 100 48. 旋转图像

news 2025/5/5 11:45:15

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