22
05/2015
[LeetCode] Rotate Image
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?
解题思路：
题目要求原地算法。假设坐标轴如上所示。顺时针旋转90度，相当于先将图片沿着x=n/2翻转，然后再将图片沿着斜对角线y=x翻转。代码如下：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int len = matrix.size();
//先将矩阵左右翻转
for(int i = 0; i<len; i++){
reverse(matrix[i]);
}
//再将矩阵沿着x=y翻转
for(int i=0; i<len; i++){
for(int j=0; j<len - i; j++){
int temp = matrix[i][j];
matrix[i][j]=matrix[len-j-1][len-i-1];
matrix[len-j-1][len-i-1]=temp;
}
}
}
void reverse(vector<int>& v){
int len = v.size();
int i=0, j=len-1;
while(i<j){
swap(v, i, j);
i++;
j--;
}
}
void swap(vector<int>& v, int i, int j){
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
};转载请注明：康瑞部落 » [LeetCode] Rotate Image
0 条评论