当前位置：首页 > news >正文

020旋转图像

news 2026/5/7 19:52:27

旋转图像

题目链接：https://leetcode.cn/problems/rotate-image/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

public void rotate(int[][] matrix) { int n = matrix.length; int temp, pre; int row=0, column, newRow=0, newColumn, tempRow; while(row<n/2){ for(column=row; column<n-1-row; column++){ temp = matrix[row][column]; newRow = column; newColumn = n-1-row; for(int i=0; i<4; 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 i=0; i<n/2; i++){ for(int j=0; j<(n+1)/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 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; } } //按主对角线翻转 for(int i=0; i<n; i++){ for(int j=0; j<i; 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]）、几何直观理解、线性代数角度分别进行分析。