• 监察体制改革后 湘西半年72名公职人员主动交代问题 2019-05-12
  • 媒体宣传报道重庆日报 王国平:扮靓重庆两江四岸” 让城市有机更新 2019-04-26
  • 我相信“交警雨中护送高考生”是真,“交警雨中护送高考生”反被该高考生家长投诉是假。 2019-04-16
  • 14名消防员日巡逻28公里 洗冷水澡 2019-04-10
  • 靶壕有了“蓝军”,百发百中的“神枪手”练起来 2019-04-10
  • 不是秀强大了,别人就会来做朋友,这逻辑不对 2019-04-01
  • 候选企业:中国石油呼和浩特石化公司 2019-03-26
  • 航天员沙漠野外生存训练完美收官!为第一天团打call 2019-03-25
  • 请问,建立市场经济后,原计划经济哪里去?改革后,我们还在实行计划经济,为何没有提及? 2019-03-25
  • 构建年轻干部梯次培养链 2019-03-19
  • 孙实的专栏作者中国国家地理网 2019-03-15
  • 湖南师范大学举行研究阐释党的十九大精神国家社科基金重大专项学术研讨会 2019-03-15
  • [雷人]蠢货!土地处于不同的城市和地段,关联的资源不一样,价值也不一样。不然给咱俩同样面积的土地,咱的在北上广深,你的在边远山区,你干么? 2019-03-08
  • 国际社会持续热议上合青岛峰会:上合组织发展进入新阶段 彰显中国领导力 2019-03-08
  • 珍惜野生动物频现甘孜境内 生态环境质量不断提升 2019-03-06
  • 频道栏目
    神奇公式秒杀全国11选5 > 程序开发 > 软件开发 > C++ > 正文
    LeetCode --- Rotate Image
    2015-03-03 14:57:48         来源:makuiyu的专栏  
    收藏   我要投稿

    题目链接:Rotate Image

    You are given an n x n 2D matrix representing an image.

    Rotate the image by 90 degrees (clockwise).

    Follow up:

    Could you do this in-place?

    这道题的要求是将n*n的矩阵顺时针旋转90°,要求原地旋转,即不申请额外空间。

    山西十一选五前三直选遗漏数据:1. 逐个旋转

    神奇公式秒杀全国11选5 www.2zfa.com 要旋转[i, j]位置的元素,即按顺序移动数组元素[i, j] -> [j, n-i-1] -> [n-i-1, n-j-1] -> [n-j-1, i] -> [i, j]。

    时间复杂度:O(n2)

    空间复杂度:O(1)

     1 class Solution
     2 {
     3 public:
     4     void rotate(vector > &matrix)
     5     {
     6         int n = matrix.size();
     7         for(int i = 0; i < n / 2; ++ i)
     8             for(int j = i; j < n - i - 1; ++ j)
     9             {
    10                 int temp = matrix[i][j];
    11                 matrix[i][j] = matrix[n - j - 1][i];
    12                 matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
    13                 matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
    14                 matrix[j][n - i - 1] = temp;
    15             }
    16     }
    17 };

    或者

     1 class Solution
     2 {
     3 public:
     4     void rotate(vector > &matrix)
     5     {
     6         int n = matrix.size();
     7         for(int i = 0; i < n / 2; ++ i)
     8             for(int j = i; j < n - i - 1; ++ j)
     9             {
    10                 swap(matrix[i][j], matrix[n - j - 1][i]);
    11                 swap(matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1]);
    12                 swap(matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1]);
    13             }
    14     }
    15 };

    2. 先翻转,在对换

    思路如下:

    1 2 3     7 8 9     7 4 1
    4 5 6  => 4 5 6  => 8 5 2
    7 8 9     1 2 3     9 6 3
    

    先将数组从上到下翻转,然后按左对角线交换对称元素。

    时间复杂度:O(n2)

    空间复杂度:O(1)

     1 class Solution
     2 {
     3 public:
     4     void rotate(vector > &matrix)
     5     {
     6         reverse(matrix.begin(), matrix.end());
     7         for(int i = 0; i < matrix.size(); ++ i)
     8             for(int j = 0; j < i; ++ j )
     9                 swap(matrix[i][j], matrix[j][i]);
    10     }
    11 };

     

    点击复制链接 与好友分享!回本站首页
    相关TAG标签
    上一篇:[LeetCode]132.Palindrome Partitioning II
    下一篇:LeetCode --- Permutations II
    相关文章
    图文推荐
    点击排行

    关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 神奇公式秒杀全国11选5

    版权所有: 神奇公式秒杀全国11选5--致力于做实用的IT技术学习网站

  • 监察体制改革后 湘西半年72名公职人员主动交代问题 2019-05-12
  • 媒体宣传报道重庆日报 王国平:扮靓重庆两江四岸” 让城市有机更新 2019-04-26
  • 我相信“交警雨中护送高考生”是真,“交警雨中护送高考生”反被该高考生家长投诉是假。 2019-04-16
  • 14名消防员日巡逻28公里 洗冷水澡 2019-04-10
  • 靶壕有了“蓝军”,百发百中的“神枪手”练起来 2019-04-10
  • 不是秀强大了,别人就会来做朋友,这逻辑不对 2019-04-01
  • 候选企业:中国石油呼和浩特石化公司 2019-03-26
  • 航天员沙漠野外生存训练完美收官!为第一天团打call 2019-03-25
  • 请问,建立市场经济后,原计划经济哪里去?改革后,我们还在实行计划经济,为何没有提及? 2019-03-25
  • 构建年轻干部梯次培养链 2019-03-19
  • 孙实的专栏作者中国国家地理网 2019-03-15
  • 湖南师范大学举行研究阐释党的十九大精神国家社科基金重大专项学术研讨会 2019-03-15
  • [雷人]蠢货!土地处于不同的城市和地段,关联的资源不一样,价值也不一样。不然给咱俩同样面积的土地,咱的在北上广深,你的在边远山区,你干么? 2019-03-08
  • 国际社会持续热议上合青岛峰会:上合组织发展进入新阶段 彰显中国领导力 2019-03-08
  • 珍惜野生动物频现甘孜境内 生态环境质量不断提升 2019-03-06