48. Rotate Image

Medium

Description

給定一個 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#

核心思路：先沿主對角線轉置（transpose），再左右翻轉每一行，等同順時針旋轉 90 度。

直接旋轉需要追蹤四個位置的循環交換，容易出錯
拆解成兩步：轉置 + 翻轉，每步都很簡單
順時針 90 度 = 轉置 + 左右翻轉；逆時針 90 度 = 轉置 + 上下翻轉

Approaches#

1: 四角循環交換#

概念: 一圈一圈處理，每次同時交換四個角落的元素
時間複雜度: O(n^2) - 每個元素恰好被訪問一次
空間複雜度: 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: 轉置 + 翻轉#

概念: 先沿主對角線轉置矩陣（交換 matrix[i][j] 和 matrix[j][i]），再左右翻轉每一行
時間複雜度: O(n^2) - 兩次遍歷矩陣
空間複雜度: 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--
            }
        }
    }
}

補充：旋轉方向整理

操作	結果
轉置 + 左右翻轉	順時針 90 度
轉置 + 上下翻轉	逆時針 90 度
上下翻轉 + 左右翻轉	旋轉 180 度

🔑 Takeaways#

Pattern: 矩陣旋轉可拆解為轉置 + 翻轉的組合
關鍵技巧: 記住「轉置 + 左右翻轉 = 順時針 90 度」，面試中快速實作且不易出錯