题解 | 顺时针旋转矩阵

1、解题思路

1. 直接旋转法： 创建一个新的 NxN 矩阵。遍历原矩阵，将原矩阵的第 i 行变为新矩阵的第 N-i-1 列。
2. 原地旋转法（进阶要求）： 先对矩阵进行转置（行列互换）。然后对每一行进行反转。

原地旋转法满足空间复杂度 O(1) 的要求，因为不需要额外的存储空间。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param mat int整型vector<vector<>>
     * @param n int整型
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > rotateMatrix(vector<vector<int> >& mat, int n) {
        // write code here
        // 直接旋转
        vector<vector<int>> rotated(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                rotated[j][n - 1 - i] = mat[i][j];
            }
        }
        return rotated;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @param n int整型 
     * @return int整型二维数组
     */
    public int[][] rotateMatrix (int[][] mat, int n) {
        // write code here
        // 直接旋转法
        int[][] rotated = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                rotated[j][n - 1 - i] = mat[i][j];
            }
        }
        return rotated;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param mat int整型二维数组 
# @param n int整型 
# @return int整型二维数组
#
class Solution:
    def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
        # write code here
        # 直接旋转法
        rotated = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                rotated[j][n - 1 - i] = mat[i][j]
        return rotated

原地旋转 O(1)

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param mat int整型vector<vector<>>
     * @param n int整型
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > rotateMatrix(vector<vector<int> >& mat, int n) {
        // write code here
        // 原地旋转法
        // 先转置
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                swap(mat[i][j], mat[j][i]);
            }
        }

        // 再反转每一行
        for (int i = 0; i < n; ++i) {
            reverse(mat[i].begin(), mat[i].end());
        }
        
        return mat;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型二维数组 
     * @param n int整型 
     * @return int整型二维数组
     */
    public int[][] rotateMatrix (int[][] mat, int n) {
        // write code here
        // 原地旋转法
        // 先转置
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        // 再反转每一行
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n / 2; ++j) {
                int temp = mat[i][j];
                mat[i][j] = mat[i][n - 1 - j];
                mat[i][n - 1 - j] = temp;
            }
        }
        return mat;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param mat int整型二维数组 
# @param n int整型 
# @return int整型二维数组
#
class Solution:
    def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
        # write code here
        # 原地旋转法
        # 先转置
        for i in range(n):
            for j in range(i, n):
                mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
        # 再反转每一行
        for i in range(n):
            mat[i].reverse()
        return mat

3、复杂度分析

1. 直接旋转法： 创建一个新矩阵，将原矩阵的行变为新矩阵的列，顺序相反。空间复杂度O(N^2^)，因为需要额外的存储空间。
2. 原地旋转法： 先对矩阵进行转置（行列互换）。然后对每一行进行反转。空间复杂度O(1)，因为不需要额外的存储空间。
3. 时间复杂度：均为O(N^2^)，因为需要遍历整个矩阵。