1006
[LeetCode]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?
【題意】
給定一個n*n個2維矩陣來表示一個圖。在原矩陣上旋轉圖形90°。
【分析】
思路1：
A[0][0] -> A[0][3]A[1][0] -> A[0][2]
A[0][1] -> A[1][3]A[2][0] -> A[0][1]
A[0][2] -> A[2][3]A[3][0] -> A[0][0]
A[0][3] -> A[3][3]
由此可得：對於n * n 的2維矩陣
A[i][j] -> A[j][n-1-i]
思路2：
純模擬，從外到內一圈一圈的轉，但這個方法太慢。
A[i][j] -> A[j][n-1-i] -> A[n-1-i][n-1-j] -> A[n-1-j][i] -> A[i][j]
思路3：
【代碼1】
/*********************************
* 日期：2014-01-21
* 作者：SJF0115
* 題號: Rotate Image
* 來源：https://oj.leetcode.com/problems/rotate-image/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <malloc.h>
#include <vector>
using namespace std;
class Solution {
public:
void rotate(vector<vector<int> > &matrix) {
int i,j;
int n = matrix.size();
vector<vector<int> >tempMatrix = matrix;
for(i = 0;i < n;i++){
for(j = 0;j < n;j++){
tempMatrix[j][n-1-i] = matrix[i][j];
}//for
}//for
for(i = 0;i < n;i++){
for(j = 0;j < n;j++){
matrix[i][j] = tempMatrix[i][j];
}//for
}//for
}
};
int main() {
Solution solution;
vector<int> row1 = {1,2,3};
vector<int> row2 = {4,5,6};
vector<int> row3 = {7,8,9};
vector<vector<int>> matrix;
matrix.push_back(row1);
matrix.push_back(row2);
matrix.push_back(row3);
solution.rotate(matrix);
int n = matrix.size();
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
printf("%d ",matrix[i][j]);
}//for
printf("\n");
}//for
return 0;
}
原地旋轉，不能使用額外的空間存儲矩陣。雖然本代碼能AC，但是不符合題意。
【代碼2】
class Solution {
public:
void rotate(vector<vector<int> > &matrix) {
int i,j,temp;
int n=matrix.size();
for(i = 0;i < n/2;++i) {
for (j = i;j < n-1-i;++j) {
temp = matrix[j][n-i-1];
matrix[j][n-i-1] = 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] = temp;
}//for
}//for
}
};
【代碼3】
class Solution {
public:
void rotate(vector<vector<int> > &matrix) {
int i,j,temp;
int n=matrix.size();
// 沿著副對角線反轉
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - i; ++j) {
temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
matrix[n - 1 - j][n - 1 - i] = temp;
}
}
// 沿著水平中線反轉
for (int i = 0; i < n / 2; ++i){
for (int j = 0; j < n; ++j) {
temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - i][j];
matrix[n - 1 - i][j] = temp;
}
}
}
};
最後更新：2017-04-03 12:54:44