摘要: 【题目】 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? ...
【题目】
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; } } }};
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。