NC18—順時針旋轉矩陣

題意

有一個 N x N 整數矩陣，請編寫一個算法，将矩陣順時針旋轉90度。

題解

方法一：使用輔助數組

觀察數組旋轉前後的位置，可以得出矩陣中的元素

matrix[row][col]

，旋轉後的新位置為

matrix[col][n-row-1]

這樣一來，我們可以建立一個與

matrix

大小相同的輔助數組，周遊原數組，依次放到輔助數組即可

時間複雜度為 O ( n 2 ) O(n^2) O(n2)，空間複雜度為 O ( n 2 ) O(n^2) O(n2)

方法二：原地旋轉

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
};
           

時間複雜度為 O ( n 2 ) O(n^2) O(n2)，空間複雜度為 O ( 1 ) O(1) O(1)

方法三：用翻轉代替旋轉

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

時間複雜度為 O ( n 2 ) O(n^2) O(n2)，空間複雜度為 O ( 1 ) O(1) O(1)

參考

旋轉矩陣