020旋转图像

旋转图像题目链接https://leetcode.cn/problems/rotate-image/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public void rotate(int[][] matrix) { int n matrix.length; int temp, pre; int row0, column, newRow0, newColumn, tempRow; while(rown/2){ for(columnrow; columnn-1-row; column){ temp matrix[row][column]; newRow column; newColumn n-1-row; for(int i0; i4; i){ pre matrix[newRow][newColumn]; matrix[newRow][newColumn] temp; temp pre; tempRow newRow; newRow newColumn; newColumn n-1-tempRow; } } row; } }分析代码的时间复杂度为O(n^2)空间复杂度为O(1)。解题思路从一个起始位置开始循环完成这组位置的交换每一组只需4次交换我们将矩阵分层从外层开始向内层每层只需要n-1个位置0~n-2列进行循环交换即可完成这层所有数据的旋转。看了官方题解后的解答//方法一使用辅助数组 //时间复杂度O(n^2) //空间复杂度O(n^2) //经过观察发现旋转90°后的矩阵第i行成为了倒数第i列利用这个规律可以使用辅助数组简单的完成旋转 public void rotate(int[][] matrix) { int n matrix.length; int[][] matrix_new new int[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { matrix_new[j][n - i - 1] matrix[i][j]; } } for (int i 0; i n; i) { for (int j 0; j n; j) { matrix[i][j] matrix_new[i][j]; } } } //方法二原地旋转 //时间复杂度O(n^2) //空间复杂度O(1) public void rotate(int[][] matrix) { int n matrix.length; int temp; for(int i0; in/2; i){ for(int j0; j(n1)/2; j){ temp matrix[i][j]; matrix[i][j] matrix[n-1-j][i]; matrix[n-1-j][i] matrix[n-1-i][n-1-j]; matrix[n-1-i][n-1-j] matrix[j][n-1-i]; matrix[j][n-1-i] temp; } } } //方法三用翻转代替旋转 //时间复杂度O(n^2) //空间复杂度O(1) public void rotate(int[][] matrix) { int n matrix.length; int temp; //上下水平翻转 for(int i0; in/2; i){ for(int j0; jn; j){ temp matrix[i][j]; matrix[i][j] matrix[n-1-i][j]; matrix[n-1-i][j] temp; } } //按主对角线翻转 for(int i0; in; i){ for(int j0; ji; j){ temp matrix[i][j]; matrix[i][j] matrix[j][i]; matrix[j][i] temp; } } }分析​ 1、方法二的解题思路结合方法一中发现的规律“旋转90°后的矩阵第i行成为了倒数第i列”我们可以得到每组数据4个的坐标然后用一个临时变量temp保存其中一个数据即可完成这组数据的旋转变换对于整个矩阵我们只需要以矩阵左上角四分之一的数据为起点完成对应每组数据的旋转交换即可完成整个矩阵的旋转。​ 2、方法三的解题思路可从坐标变换公式能推导出关键等式matrix[row] [col] matrix[col] [n-1-row]、几何直观理解、线性代数角度分别进行分析。总结本题主要需要经过观察总结出关键等式matrix[row] [col] matrix[col] [n-1-row]寻找到能够满足这个等式的方法或直接根据等式推断出每组数据的坐标然后进行旋转替换或采用水平翻转对角线翻转从而实现矩阵90°旋转。方法三的逻辑清晰且更加通用。