給定一個 n x n 的 2D 矩陣
matrix，將其原地順時針旋轉 90 度。不能使用額外的矩陣空間。
Example:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]
Intuition
TIP
核心思路：先沿主對角線轉置（transpose），再左右翻轉每一行，等同順時針旋轉 90 度。
- 直接旋轉需要追蹤四個位置的循環交換，容易出錯
- 拆解成兩步：轉置 + 翻轉，每步都很簡單
- 順時針 90 度 = 轉置 + 左右翻轉；逆時針 90 度 = 轉置 + 上下翻轉
Approaches
1. Four-Corner Cyclic Swap — O(n^2) / O(1)
- Idea: 一圈一圈處理，每次同時交換四個角落的元素
- Time:
O(n^2)- 每個元素恰好被訪問一次 - Space:
O(1)- 原地操作
class Solution {
fun rotate(matrix: Array<IntArray>) {
val n = matrix.size
for (layer in 0 until n / 2) {
val last = n - 1 - layer
for (i in layer until last) {
val offset = i - layer
val top = matrix[layer][i]
// 左 -> 上
matrix[layer][i] = matrix[last - offset][layer]
// 下 -> 左
matrix[last - offset][layer] = matrix[last][last - offset]
// 右 -> 下
matrix[last][last - offset] = matrix[i][last]
// 上 -> 右
matrix[i][last] = top
}
}
}
}⭐ 2. Transpose + Reverse — O(n^2) / O(1)
- Idea: 先沿主對角線轉置矩陣（交換 matrix[i][j] 和 matrix[j][i]），再左右翻轉每一行
- Time:
O(n^2)- 兩次遍歷矩陣 - Space:
O(1)- 原地操作
class Solution {
fun rotate(matrix: Array<IntArray>) {
val n = matrix.size
// 轉置
for (i in 0 until n) {
for (j in i + 1 until n) {
val temp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = temp
}
}
// 左右翻轉
for (i in 0 until n) {
var left = 0
var right = n - 1
while (left < right) {
val temp = matrix[i][left]
matrix[i][left] = matrix[i][right]
matrix[i][right] = temp
left++
right--
}
}
}
}Note: Rotation Directions Summary
| 操作 | 結果 |
|---|---|
| 轉置 + 左右翻轉 | 順時針 90 度 |
| 轉置 + 上下翻轉 | 逆時針 90 度 |
| 上下翻轉 + 左右翻轉 | 旋轉 180 度 |
🔑 Takeaways
- Pattern: 矩陣旋轉可拆解為轉置 + 翻轉的組合
- Key trick: 記住「轉置 + 左右翻轉 = 順時針 90 度」，面試中快速實作且不易出錯