现有一个NxN的矩阵,阶数为N,请编写一个算法将矩阵顺时针旋转90度并将其作为返回值。要求不使用缓存矩阵,保证N不大于500,元素不大于256,每个元素用int表示。
测试样例:
[[1,2,3],[4,5,6],[7,8,9]],3
返回:[[7,4,1],[8,5,2],[9,6,3]]
import java.util.*; /* 思路:逐层旋转,最外层向内,其中layer表示当前所处理的层, 每次都是n*n矩阵中可以形成方阵中的四个数进行旋转, 左->上,下->左,右->下,上->右的顺序, 在第一步之前先存储“上”中的值*/ public class Transform { public int[][] transformImage(int[][] mat, int n) { // write code here for(int layer = 0;layer < n/2; layer++){ int first = layer; int last = n-1-layer; for(int i = first; i < last; i++){ int offset = i - first; int top = mat[first][i]; //left -> top mat[first][i] = mat[last - offset][first]; //bottom -> left mat[last-offset][first] = mat[last][last-offset]; //right -> bottom mat[last][last-offset] = mat[i][last]; //top -> right mat[i][last] = top; } } return mat; } }
public int[][] transformImage(int[][] mat, int n) { for (int i = 0; i < n >> 1; i++) { for (int j = i; j < n - 1 - i; j++) { int k = mat[i][j]; mat[i][j] = mat[n - 1 - j][i]; mat[n - 1 - j][i] = mat[n - 1 - i][n - 1 - j]; mat[n - 1 - i][n - 1 - j] = mat[j][n - 1 - i]; mat[j][n - 1 - i] = k; } } return mat; }
别人的思路: 首先上下翻转,再按照主对角线翻转1 2 3 7 8 9 7 4 14 5 6 —> 4 5 6 ---> 8 5 27 8 9 1 2 3 9 6 3vector<vector<int> > transformImage(vector<vector<int> > mat, int n) { //上下交换 for(int i = 0; i < n/2; ++i){ for(int j = 0; j < n; ++j){ swap(mat[i][j], mat[n-1-i][j]); } } //主对角线交换 for(int i = 0; i < n; ++i){ for(int j = i+1; j < n; ++j){ swap(mat[i][j], mat[j][i]); } } return mat; }
vector<vector<int> > transformImage(vector<vector<int> > mat, int n) { // write code here int i,j,temp=0; for (i=0;i<n;i++) { for (j=0;j<n/2;j++) { temp=mat[i][j]; mat[i][j]=mat[i][n-1-j]; mat[i][n-1-j]=temp; } } for (i=0;i<n;i++) { for (j=0;j<n-i;j++) { temp=mat[i][j]; mat[i][j]=mat[n-1-j][n-1-i]; mat[n-1-j][n-1-i]=temp; } } return mat; }
class Transform { public: vector<vector<int> > transformImage(vector<vector<int> > mat, int n) { // write code here //转置 vector< vector<int> > a = mat; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) swap(a[i][j], a[j][i]); // 左右镜像 for(int i =0; i < n;i++) for(int j = 0; j < n/2; j++) swap(a[i][j], a[i][n-j-1]); return a; } };
}
1 2 3 7 4 1 4 5 6 --> 8 5 2 7 8 9 9 6
3
翻转90度,即将原二维数组的第一行转为数组2的最后一列,第二行变为第二列,依次类推。。。 实现:建一个同大小的空二维数组,从最后一列开始,将原数组第一行复制到新数组最后一列,依次类推。代码如下:
public class Transform {
public int[][] transformImage(int[][] mat, int n) {
// write code here
int[][] copymat = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
copymat[j][n-1-i] = mat[i][j];
}
}
return copymat;
}
}
public int[][] transformImage(int[][] mat, int n) { // write code here //对矩阵副对角线上的元素进行交换。 for (int i = 0; i < n; i++) { int temp = 0; for (int j = i+1; j < n; j++) { temp = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = temp; } } //再将0~n-1列进行两两对称交换。 int i = 0; int j = n-1; while (i < j){ int k = 0; int temp = 0; while (k < n){ temp = mat[k][i]; mat[k][i] = mat[k][j]; mat[k][j] = temp; k++; } ++i; --j; } return mat; }
vector<vector<int> > tranformImage(vector<vector<int> > mat, int n) { // write code here int i,j,t; for( i=0;i<n;i++) { for( j=i+1;j<n;j++) { t=mat[i][j]; mat[i][j]=mat[j][i]; mat[j][i]=t; } } return mat; }
class Transform { public: vector<vector<int> > transformImage(vector<vector<int> > mat, int n) { if(n<=1) return mat; for(int i=0;i<n-1;++i) for(int j=0;i+j<n-1;++j) swap(mat[i][j],mat[n-1-j][n-1-i]); for(int k=0;k<n/2;++k) swap(mat[k],mat[n-1-k]); return mat; } };
import java.util.*; public class Transform { // 顺时针旋转,先上下翻,在沿着对角线翻 // 逆时针旋转,先沿对角线翻,再上下翻 public int[][] transformImage(int[][] mat, int n) { // write code here // 上下翻转 mat[i][j] ==> mat[n-1-i][j] for(int i=0;i<n/2;i++) { for(int j=0;j<n;j++) { int a = mat[i][j]; mat[i][j] = mat[n-1-i][j]; mat[n-1-i][j] = a; } } // 沿着对角线翻转 mat[i][j] ==> mat[j][i] for(int i=0;i<n;i++) { for(int j=0;j<i;j++) { int a = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = a; } } return mat; } }顺时针和逆时针都一样思路的翻转方法
class Transform { public: vector<vector<int> > transformImage(vector<vector<int> > mat, int n) { for(int layer = 0;layer<n/2;++layer){ int first = layer; int last = n-1-layer; //对每个圈进行旋转 for(int i = first;i<last;++i){ int offset = i-first;//偏置量 int top = mat[first][i]; mat[first][i]=mat[last-offset][first]; mat[last-offset][first] = mat[last][last-offset]; mat[last][last-offset] = mat[i][last]; mat[i][last] = top; } } return mat; } };
vector<vector<int>> c=mat;vector< vector<int> > c(n, vector<int>(n));for (int i = 0; i < n; i++)
import java.util.*; public class Transform { public int[][] transformImage(int[][] mat, int n) { int arrNew[][]=new int[n][n]; int num=n-1; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ arrNew[i][j]=mat[num][i]; num--; } num=n-1; } return arrNew; } }
class Transform { public: vector<vector<int> > transformImage(vector<vector<int> > mat, int n) { // write code here for (int i=0;i<n/2;i++){ for (int j=i;j<n-i-1;j++){ int mid=mat[i][j]; mat[i][j]=mat[n-j-1][i]; mat[n-j-1][i]=mat[n-i-1][n-j-1]; mat[n-i-1][n-j-1]=mat[j][n-i-1]; mat[j][n-i-1]=mid; } } return mat; } };