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

顺时针旋转矩阵

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

思路

题目分析

  1. 题目给出的输入有一个N*N大小的数组,并且给出了维数N
  2. 我们需要返回这个数组顺时针翻转90度后的数组
  • 方法一:开辟新数组按照索引关系装填
    • 我们申请一个同样空间大小的新的二维数组ans来承接原数组mat的元素
    • 90度翻转的数组和原数组存在索引上的关系符合ans[j][n-i-1] = mat[i][j]
    • 依照这个关系双重循环即可
  • 方法二:原地旋转
    • 原地我们无法直接进行旋转,因此我们要找90度前后的位置关系
    • 原数组经过水平翻转,再将对角线翻转可以得到90度的顺时针旋转
    • 依据这一规律,我们将原数组原地旋转

方法一:按照索引关系

class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        // write code here
      vector<vector<int>> ans(n,vector<int>(n));	// 申请新的N*N空间
      for(int i = 0; i < n; i++){
          for(int j = 0; j < n; j++){
              ans[j][n - 1 - i] = mat[i][j];  	  // 按照索引关系重新装填
          }
      }
      return ans;
    }
};

复杂度分析

  • 时间复杂度:O(N2)O(N^2)O(N2),使用了双重循环
  • 空间复杂度:O(N2)O(N^2)O(N2),申请了ans的二维数组空间

方法二:原地旋转

alt

class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        // write code here
        //水平翻转
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                swap(mat[i][j], mat[n - i - 1][j]);		// 水平翻转只要更改行的对称索引即可
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                swap(mat[i][j], mat[j][i]);				// 对角线翻转只要交换行与列索引即可
            }
        }
        return mat;
    }
};

复杂度分析

  • 时间复杂度:O(N2)O(N^2)O(N2),使用了双重循环
  • 空间复杂度:O(1)O(1)O(1),未申请额外空间
不会做题写的题解 文章被收录于专栏

哎呀我好笨呀,一不小心又不会了一道题

全部评论

相关推荐

06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
07-09 18:28
门头沟学院 Java
写着提前批,结果还要实习4个月以上???
程序员牛肉:这种不用看,直接投了,面试的时候问对应的HR就行。有可能他们是直接复制的暑期实习的模板。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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