48. 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?
要将image旋转90度,其实就是将矩阵旋转90度,以下面这个矩阵为例:
1 2 3
4 5 6
7 8 9
想要将其顺时针旋转90度,可以先以中间行为轴,上下对应行进行交换,对于这个例子,矩阵在经过这样的变化后,变成:
7 8 9
4 5 6
1 2 3
之后对矩阵进行转置运算,得:
7 4 1
8 5 2
9 6 3
这也就是我们对原矩阵进行顺时针旋转后得到的矩阵,到这里,就可以很容易地写出代码了:
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int i=0,j=0,row=matrix.size(),col=matrix[0].size(),tmp=0;
int low=0,high=matrix.size()-1;
while(low<high)
swap(matrix[low++],matrix[high--]);
for(i=0;i<row;i++){
for(j=i+1;j<col;j++)
swap(matrix[i][j],matrix[j][i]);
}
}
};
时间复杂度为O(n),空间复杂度为O(1),符合题目中要求的constant-place