频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
LeetCode --- Rotate Image
2019-07-21 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. 逐个旋转

要旋转[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技术培训 | 举报中心

版权所有: 全峰安全联盟--致力于做实用的IT技术学习网站