题解 | #顺时针旋转矩阵#

题目主要信息:

• 给定一个$n\ast nn*n$的矩阵，返回其顺时针90度旋转后的结果

具体思路:

这道题可能需要将矩阵画出来，观察一下旋转后的规律：

乍一看没有啥规律，但是旋转后的第一行是不是与原矩阵的第一列很像，就是其翻转之后的结果，那我们可以再尝试画出一个顺时针90度旋转后每行翻转的矩阵： 然后我们会惊喜得发现，这就是互为转置的两个矩阵（转置矩阵为上三角矩阵元素与下三角矩阵元素依据对角线位置互换的矩阵）。因为转置的可逆性，只要过程逆转，就可以得到顺时针旋转90度后的矩阵了。

• step 1：遍历矩阵的下三角矩阵，将其与上三角矩阵对应的位置互换，其实就是数组下标交换后的互换。
• step 2：遍历矩阵每一行，将每一行看成一个数组使用reverse函数翻转。

代码实现:

class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        for(int i = 0; i < n; i++) //矩阵转置
            for(int j = 0; j < i; j++)
                swap(mat[i][j], mat[j][i]);
        for(int i = 0; i < n; i++) //每行翻转
            reverse(mat[i].begin(), mat[i].end());
        return mat;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，转置需要遍历矩阵，逐行翻转也是$O(n^2)O(n^2)$
• 空间复杂度：$O(1)O(1)$，没有使用额外辅助空间