题目描述
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
解题思路
- 首先以从对角线为轴翻转，然
- 后再以x轴中线上下翻转即可得到结果，如下图所示：
1 2 3 9 6 3 7 4 1
4 5 6 –> 8 5 2 –> 8 5 2
7 8 9 7 4 1 9 6 3
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i = 0; i < n - 1; i++){ // 只是左上角部分
for(int j = 0; j < n - i - 1; j++){
swap(matrix[i][j], matrix[n - j - 1][n - i - 1]);
}
}
reverse(matrix.begin(), matrix.end());
}
};
解题思路
- 本质上是矩阵顺时针旋转90度
- 我们按顺时针的顺序去覆盖前面的数字，从四个顶角开始，然后往中间去遍历，每次覆盖的坐标都是同理，如下：
(i, j) <- (n-1-j, i) <- (n-1-i, n-1-j) <- (j, n-1-i)
- 这其实是个循环的过程，第一个位置又覆盖了第四个位置，这里i的取值范围是 [0, n/2)，j的取值范围是 [i, n-1-i)，至于为什么i和j是这个取值范围，为啥i不用遍历 [n/2, n)，若仔细观察这些位置之间的联系，不难发现，实际上j列的范围 [i, n-1-i) 顺时针翻转 90 度，正好就是i行的 [n/2, n) 的位置，这个方法每次循环换四个数字，如下所示：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for(int i = 0; i < n / 2; i++){
for(int j = i; j < n - 1 - i; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - 1 - j];
matrix[n - i - 1][n - 1 - j] = matrix[j][n - 1 - i];
matrix[j][n - 1 - i] = tmp;
}
}
}
};
