题解 | #顺时针旋转矩阵#
顺时针旋转矩阵
http://www.nowcoder.com/practice/2e95333fbdd4451395066957e24909cc
1、模拟
利用空间复杂度O(n^2)新数组的空间，时间复杂度O(n^2)
public int[][] rotateMatrix(int[][] mat, int n) {
// write code here
int[][]arr = new int[n][n];
for(int i = 0;i<n;i++){
for(int j =0;j<n;j++){
arr[i][j]=mat[n-j-1][i];
}
}
return arr;
}
2、原地交换：时间复杂度O(n^2)需要遍历两次数组，空间复杂度O(1)
思路：先沿着左对角线折叠折叠交换数组元素，然后再沿着竖轴交换元素
沿着左对角线交换元素
for(int i = 0;i<n;i++){
//一定不能写成j<n,否则就又会变成原数组，可以画图试试
for(int j = 0;j<i;j++){
temp = mat[i][j];
mat[i][j]= mat[j][i];
mat[j][i]= temp;
}
}
沿着竖轴交换元素
for(int i = 0;i<n;i++){
//这里一定要是长度的一半，否在交换了两次又变成了原来的样子
for(int j = 0;j<n/2;j++){
temp = mat[i][j];
mat[i][j] = mat[i][n-j-1];
mat[i][n-j-1]=temp;
}
}
代码汇总
public int[][] rotateMatrix(int[][] mat, int n) {
//首先矩阵沿着左对象线翻转
int temp;
for(int i = 0;i<n;i++){
for(int j = 0;j<i;j++){
temp = mat[i][j];
mat[i][j]= mat[j][i];
mat[j][i]= temp;
}
}
//对竖轴进行进行翻转
for(int i = 0;i<n;i++){
for(int j = 0;j<n/2;j++){
temp = mat[i][j];
mat[i][j] = mat[i][n-j-1];
mat[i][n-j-1]=temp;
}
}
return mat;
}
思考，如何用上述思路逆时针旋转数组呢？
是不是可以先沿着竖轴交换，然后沿着左对角线交换就行了
