LeetCode 48：旋轉圖像——原地順時針旋轉 90 度的矩陣變換

題目描述

給定 n×n 矩陣，原地順時針旋轉 90 度。

等價變換

順時針 90° = 主對角線轉置 + 水平中線翻轉（或先水平翻轉再轉置）。

• 轉置：swap(matrix[i][j], matrix[j][i]) for i < j。
• 水平翻轉：swap(matrix[i][j], matrix[i][n-1-j]) for j < n/2。

C++ 代碼

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 主對角線轉置
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                swap(matrix[i][j], matrix[j][i]);
        // 水平翻轉
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n/2; ++j)
                swap(matrix[i][j], matrix[i][n-1-j]);
    }
};

驗證示例

原矩陣:          轉置後:          翻轉後(結果):
1 2 3            1 4 7            7 4 1
4 5 6     =>     2 5 8     =>     8 5 2
7 8 9            3 6 9            9 6 3

複雜度

• 時間：O(n²)，每個元素移動常數次。
• 空間：O(1) 原地操作。

總結

矩陣旋轉通過分解為基本幾何變換（轉置+翻轉）實現原地操作。同理，逆時針 90° = 轉置 + 垂直翻轉；180° = 水平翻轉 + 垂直翻轉。