LeetCode 热题 100 48. 旋转图像

LeetCode 热题 100 | 48. 旋转图像

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

---

问题描述

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

1. 输入: matrix = [[1,2,3],[4,5,6],[7,8,9]]
2. 输出: [[7,4,1],[8,5,2],[9,6,3]]

复制代码

示例2：

1. 输入: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
2. 输出: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

复制代码

---

解题思绪

焦点头脑

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

---

Python代码实现

1. def rotate(matrix):
2.     n = len(matrix)
3.    
4.     # 转置矩阵
5.     for i in range(n):
6.         for j in range(i, n):
7.             matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
8.    
9.     # 反转每一行
10.     for i in range(n):
11.         matrix[i].reverse()
13. # 测试示例
14. matrix1 = [[1,2,3],[4,5,6],[7,8,9]]
15. matrix2 = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
17. rotate(matrix1)
18. rotate(matrix2)
20. print(matrix1)  # 输出: [[7,4,1],[8,5,2],[9,6,3]]
21. 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[j] 和 matrix[j]，实现转置。
    
  
  
• 反转每一行：
  
  
  
  • 使用 reverse() 方法对每一行进行反转。
    
  
  
• 原地操作：
  
  
  
  • 直接在原矩阵上进行转置和反转，不需要额外的空间。
    
  
  

---

复杂度分析

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

---

示例运行

示例1

1. 输入: matrix = [[1,2,3],[4,5,6],[7,8,9]]
2. 输出: [[7,4,1],[8,5,2],[9,6,3]]

复制代码

示例2

1. 输入: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
2. 输出: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

复制代码

---

进阶：其他解法

方法一：四角旋转

1. def rotate_four_corners(matrix):
2.     n = len(matrix)
3.     for i in range(n // 2):
4.         for j in range(i, n - 1 - i):
5.             # 保存左上角的值
6.             temp = matrix[i][j]
7.             # 左下角 → 左上角
8.             matrix[i][j] = matrix[n - 1 - j][i]
9.             # 右下角 → 左下角
10.             matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
11.             # 右上角 → 右下角
12.             matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
13.             # 左上角 → 右上角
14.             matrix[j][n - 1 - i] = temp
16. # 测试示例
17. matrix1 = [[1,2,3],[4,5,6],[7,8,9]]
18. matrix2 = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
20. rotate_four_corners(matrix1)
21. rotate_four_corners(matrix2)
23. print(matrix1)  # 输出: [[7,4,1],[8,5,2],[9,6,3]]
24. print(matrix2)  # 输出: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

复制代码

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

---

总结

通过使用转置 + 反转的方法，我们可以高效地将矩阵顺时针旋转90度，而且原地修改矩阵。这种方法直观且易于实现，得当大多数场景。希望这篇题解对大家有所资助，如果有任何问题，接待在批评区留言讨论！
关注我，获取更多算法题解和编程本领！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。