題目網址：https://leetcode.cn/problems/rotate-image/

題意：給一 n x n 的 2D array 表示一個 image, 請將 image 順時針旋轉 90 度。

注意：請使用 in-place 演算法

Solution 1：

想法：將 matrix 由外而內分成好幾層, 每一層依序交換以完成旋轉

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        const int n = matrix.size();

        // 想像從 (0, 0) 沿著對角線往中心點前進(n為奇數時中心不用旋轉, 故為 i < n / 2)
        for (int i = 0; i < n / 2; ++i) {
            // 每層共 n-2*(i+1) 個元素, 每往內一層元素個數就會減2, 減掉最左、最右兩個數
            // i 為起始 idx, 則 i+n-2*(i+1) = n-i-2 為結束 idx
            for (int j = i; j <= n - i - 2; ++j) {
                const int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }
};
  • time：$O(n^2)$ ➔ 遍歷 matrix
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：（進階）

想法：先將 matrix 做轉置（將同 row 的元素變成同 col）, 然後再每列做水平翻轉（reverse）
（水平翻轉：原本左邊 $1^{st}$ col 變成右邊 $1^{st}$ col, 左邊 $2^{nd}$ col 變成右邊 $2^{nd}$ col, 依此類推）

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        const int n = matrix.size();

        // 轉置
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // 每一列做 reverse
        for (int i = 0; i < n; ++i) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};
  • time：$O(n^2)$ ➔ 遍歷 matrix
  • space：$O(1)$ ➔ 只需常數空間