題目描述
給定一個 n × n 的 2D 矩陣 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]]
限制條件：
- n == matrix.length == matrix[i].length
- 1 ≤ n ≤ 20
- −1000 ≤ matrix[i][j] ≤ 1000
解題思路
這題要求原地旋轉 90度（不使用額外的矩陣），可以用數學方式找出元素移動規律來實現：
規律
假設我們有一個 n×n 矩陣：
a00 a01 a02
a10 a11 a12
a20 a21 a22
順時針旋轉 90 度後，變為：
a20 a10 a00
a21 a11 a01
a22 a12 a02
觀察元素變化規律：
(i, j)→(j, n - 1 - i)
解法一：轉置 + 反轉行
思路
- 矩陣轉置（Transpose）：將
matrix[i][j]交換為matrix[j][i]，即 沿主對角線翻轉。 - 反轉每一行（Reverse）：將轉置後的每一行反轉，即可得到旋轉後的矩陣。
實作程式碼
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 1. 轉置矩陣
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 2. 反轉每一行
for row in matrix:
row.reverse()
時間與空間複雜度分析
- 時間複雜度：O(n^2)
- 轉置矩陣需要掃描約 (n^2)/2 次，反轉行數約 O(n)，合計為 O(n^2)。
- 空間複雜度：O(1)（原地修改，不使用額外空間）。
解法二：四點旋轉（逐層旋轉）
思路
旋轉 90 度可以分解成四個角落的元素交換：
- 先選擇最外層的元素進行旋轉，每次四個點交換。
- 逐層內縮，直到所有元素都旋轉完成。
公式
對於矩陣的元素 (i, j)，旋轉後的位置：
(matrix[i][j] -> matrix[j][n-1-i] -> matrix[n-1-i][n-1-j] -> matrix[n-1-j][i] -> matrix[i][j])
實作程式碼
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 逐層旋轉
for i in range(n // 2): # 逐層處理
for j in range(i, n - i - 1): # 逐元素旋轉
# 四點旋轉
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
時間與空間複雜度分析
- 時間複雜度：O(n^2)（因為需要遍歷所有元素）。
- 空間複雜度：O(1)（原地修改，不使用額外空間）。
結論
- 如果需要原地修改，推薦使用「轉置 + 反轉行」方法，簡單且易於理解。
- 如果想深入理解矩陣旋轉的邏輯，建議使用「四點旋轉」方法。
這道題目是經典的矩陣變換題，熟練掌握後，可以應用在許多影像處理或圖形運算中！
