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;
}
思考,如何用上述思路逆时针旋转数组呢?
是不是可以先沿着竖轴交换,然后沿着左对角线交换就行了

京公网安备 11010502036488号