原地旋轉矩陣 90 度：空間最優解法圖解與實現

N×N 矩陣原地逆時針旋轉 90° 算法詳解

面試經典題目：給定 N×N 矩陣代表圖像，要求不使用額外存儲空間，將圖像逆時針旋轉 90 度。

直觀理解與兩步法

以 4×4 矩陣為例：

原圖：          逆時針 90° 後：
1  2  3  4      4  8  12 16
5  6  7  8      3  7  11 15
9  10 11 12     2  6  10 14
13 14 15 16     1  5  9  13

可分兩步完成，均為原地操作：

1. 主對角線鏡像（轉置）：交換 matrix[i][j] 與 matrix[j][i]（i < j）
2. 上下翻轉：交換第 i 行與第 N-1-i 行

過程演示

原圖：        步驟1（轉置）：    步驟2（上下翻轉）：
1 2 3 4       1 5 9 13           4 8 12 16
5 6 7 8       2 6 10 14          3 7 11 15
9 10 11 12    3 7 11 15    →     2 6 10 14
13 14 15 16   4 8 12 16          1 5 9 13

C++ 參考實現

void swap(int &x, int &y) { int t = x; x = y; y = t; }

void rotate90CounterClockwise(int matrix[][4], int n) {
    // 步驟1：主對角線鏡像（轉置）
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            swap(matrix[i][j], matrix[j][i]);

    // 步驟2：上下翻轉
    for (int i = 0; i < n / 2; ++i)
        for (int j = 0; j < n; ++j)
            swap(matrix[i][j], matrix[n - 1 - i][j]);
}

複雜度與變體

• 時間複雜度：O(N²) —— 必須訪問每個元素至少一次
• 空間複雜度：O(1) —— 僅使用常數額外空間
• 順時針 90°：先轉置，再左右翻轉（交換第 j 行與第 N-1-j 列）
• 180° 旋轉：上下翻轉 + 左右翻轉，或兩次 90° 旋轉

此法利用矩陣幾何變換分解，邏輯清晰、易於驗證，是面試與工程實踐的首選方案。