0048. 旋转图像

0048. 旋转图像 #

  • 标签:数组
  • 难度:中等

题目大意 #

给定一个 n*n 的二维矩阵(代表图像)。将二维矩阵顺时针旋转 90°,要求不能使用额外的数组空间。

解题思路 #

如果使用额外数组空间的话,将对应元素存放到对应位置即可。如果不使用额外的数组空间,则需要观察每一个位置上的点最初位置和最终位置有什么规律。

对于矩阵中第 i 行的第 j 个元素,在旋转后,它出现在倒数第 i 列的第 j 个位置。即

matrixnew[col][n−row−1] = matrix[row][col]

matrixnew[col][n-row-1] 的点经过旋转移动到了 matrix[n−row−1][n−col−1] 的位置。

matrix[n−row−1][n−col−1] 位置上的点经过旋转移动到了 matrix[n−col−1][row] 的位置。

matrix[n−col−1][row] 位置上的点经过旋转移动到了最初的 matrix[row][col] 的位置。

这样就形成了一个循环,我们只需要通过一个临时变量 tmp 就可以将循环中的点逐一进行交换。

另一种思路是利用翻转代替旋转。

原矩阵可以通过一次水平翻转+主对角线翻转得到旋转后的二维矩阵。具体可以参考代码。

代码 #

1
2
3
4
5
6
7
8
def rotate(self, matrix: List[List[int]]) -> None:
    n = len(matrix)
    for i in range(n//2):
        for j in range(n):
            matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]
    for i in range(n):
        for j in range(i):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
本站总访问量  次  |  您是本站第  位访问者