【题目】
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 * 来源:http://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; } } } };