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

---

解題思路

核心思想

1. 轉置 + 反轉：

   • 首先對矩陣進行轉置（即行變列，列變行）。
   • 然后對每一行進行反轉，即可得到順時針旋轉90度的結果。

2. 原地操作：

   • 直接在原矩陣上進行轉置和反轉操作，不需要額外的空間。

---

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

---

代碼解析

1. 轉置矩陣：

   • 使用雙重循環遍歷矩陣的上三角部分（i 從 0 到 n-1，j 從 i 到 n-1）。
   • 交換 matrix[i][j] 和 matrix[j][i]，實現轉置。

2. 反轉每一行：

   • 使用 reverse() 方法對每一行進行反轉。

3. 原地操作：

   • 直接在原矩陣上進行轉置和反轉，不需要額外的空間。

---

復雜度分析

• 時間復雜度：O(n2)，其中 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(n2)
• 空間復雜度：O(1)

---

總結

通過使用轉置 + 反轉的方法，我們可以高效地將矩陣順時針旋轉90度，并且原地修改矩陣。這種方法直觀且易于實現，適合大多數場景。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！