题目链接: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°,要求原地旋转,即不申请额外空间。
-
逐个旋转
要旋转[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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 - i - 1; ++ j)
{
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
};
或者
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 - i - 1; ++ j)
{
swap(matrix[i][j], matrix[n - j - 1][i]);
swap(matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1]);
swap(matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1]);
}
}
};
-
先翻转,在对换
思路如下:
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
2
3
4
5
6
7
8
9
10
11
class Solution
{
public:
void rotate(vector<vector<int> > &matrix)
{
reverse(matrix.begin(), matrix.end());
for(int i = 0; i < matrix.size(); ++ i)
for(int j = 0; j < i; ++ j )
swap(matrix[i][j], matrix[j][i]);
}
};