題目描述:將 n×n 矩陣順時針旋轉 90°,原地操作。
解題思路:數學觀察:順時針 90° = 先轉置(沿主對角線翻轉)再左右反轉每一行。轉置:matrix[i][j] 與 matrix[j][i] 互換。反轉每行:matrix[i][j] 與 matrix[i][n-1-j] 互換。兩步各需 O(n²) 時間,O(1) 額外空間。
時間複雜度:O(n²) — 轉置和反轉各訪問所有元素一次。
空間複雜度:O(1) — 原地操作。
1. Transpose: for i in [0,n), j in [i+1,n): swap matrix[i][j] and matrix[j][i] 2. Reverse each row: for each row, swap matrix[i][j] and matrix[i][n-1-j]
轉置再反轉列 O(n²) 時間,O(1) 空間:先轉置,再對稱反轉每列 — 等價但分兩步。
逐層旋轉 O(n²) 時間,O(1) 空間:如本解法但邏輯重複,外層迴圈計算層數。