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?
不使用额外的空间顺时针旋转方阵90度
例如
旋转后变为
算法1
先将矩阵转置，然后把转置后的矩阵每一行翻转
转置变为 
每一行翻转变为
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class
Solution {
public
:
void
rotate(vector<vector<
int
> > &matrix) {
int
n = matrix.size();
//转置
for
(
int
i = 0; i < n; i++)
for
(
int
j = i+1; j < n; j++)
swap(matrix[i][j] , matrix[j][i]);
//每一行翻转
for
(
int
i = 0; i < n; i++)
for
(
int
j = 0; j < (n>>1); j++)
swap(matrix[i][j], matrix[i][n-j-1]);
}
};
|
算法2
可以见矩阵看成多个环组成，如下4*4的矩阵包括两个环，第一个环为1,2,3,4,8,12,16,15,14,13,9,5,1，第二个环为6,7,11,10。
旋转一个矩阵，相当于把每一个环都旋转。如何旋转一个环呢？以最外层的环举例： 本文地址
旋转前：
，旋转后：
我们把环分成3组：{1,4,16,13}，{2,8,15,9}，{3,12,14,5}，每一组中：旋转后相当于把原来的数字移动到同组中下一个数字的位置
对于一个n*n的矩阵可以分成n/2（向上取整）个环来旋转；对于边长为len的环，可以分成len-1组来旋转。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class
Solution {
public
:
void
rotate(vector<vector<
int
> > &matrix) {
int
n = matrix.size();
if
(n == 0)
return
;
for
(
int
i = 0, len = n; i < n/2; i++, len -= 2)
{
//n/2 为旋转的圈数，len为第i圈中正方形的边长
int
m = len - 1;
for
(
int
j = 0; j < m; j++)
{
int
tmp = matrix[i][i+j];
matrix[i][i+j] = matrix[i+m-j][i];
matrix[i+m-j][i] = matrix[i+m][i+m-j];
matrix[i+m][i+m-j] = matrix[i+j][i+m];
matrix[i+j][i+m] = tmp;
}
}
}
};
|
本文转自tenos博客园博客，原文链接：http://www.cnblogs.com/TenosDoIt/p/3768734.html，如需转载请自行联系原作者
