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

顺时针旋转矩阵

http://www.nowcoder.com/practice/2e95333fbdd4451395066957e24909cc

题目主要信息:

  • 给定一个nnn*n的矩阵,返回其顺时针90度旋转后的结果

具体思路:

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

乍一看没有啥规律,但是旋转后的第一行是不是与原矩阵的第一列很像,就是其翻转之后的结果,那我们可以再尝试画出一个顺时针90度旋转后每行翻转的矩阵: alt 然后我们会惊喜得发现,这就是互为转置的两个矩阵(转置矩阵为上三角矩阵元素与下三角矩阵元素依据对角线位置互换的矩阵)。因为转置的可逆性,只要过程逆转,就可以得到顺时针旋转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(n2)O(n^2),转置需要遍历矩阵,逐行翻转也是O(n2)O(n^2)
  • 空间复杂度:O(1)O(1),没有使用额外辅助空间
孤帆远影碧空尽 文章被收录于专栏

牛客网各类题单题解~

全部评论

相关推荐

机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
每晚夜里独自颤抖:你cet6就cet6,cet4就cet4,你写个cet证书等是什么意思。专业技能快赶上项目行数,你做的这2个项目哪里能提现你有这么多技能呢
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 15:58
投个小米提前批试试水,先投一个岗位看看形势,不行就再沉淀一下投第二个岗位,莫辜负
Java抽象带篮子:我嘞个骚刚,已经开始研发6g了吗
投递小米集团等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务