跳转至

48 旋转图像

官方题解已经说的非常详细

https://leetcode.cn/problems/rotate-image/?envType=study-plan-v2&envId=top-100-liked

普通做法

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> newMatrix(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                newMatrix[j][n - 1 - i] = matrix[i][j];
            }
        }
        matrix.assign(newMatrix.begin(),newMatrix.end());
    }
};

原地旋转

方法一

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

复杂度分析

时间复杂度:\(O(N^2)\),其中 N 是 matrix 的边长。我们需要枚举的子矩阵大小为 \(O(⌊n/2⌋×⌊(n+1)/2⌋)=O(N^2 )\)。

空间复杂度:\(O(1)\)。为原地旋转。

方法二

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 j = 0; j < n / 2; j++) {
            for (int i = 0; i < n; i++) {
                swap(matrix[i][j], matrix[i][n - 1 - j]);
            }
        }
    }
};
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for(int i = 0; i < n; i++){
            int left = 0, right = n - 1;
            while(left < right){
                swap(matrix[i][left], matrix[i][right]);
                left++;
                right--;
            }
        }
    }
};

复杂度分析

时间复杂度:\(O(N^2)\),其中 N 是 matrix 的边长。对于每一次翻转操作,我们都需要枚举矩阵中一半的元素。

空间复杂度:\(O(1)\)。为原地翻转得到的原地旋转。