- 标签:数组
- 难度:中等
给定一个 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 就可以将循环中的点逐一进行交换。
另一种思路是利用翻转代替旋转。
原矩阵可以通过一次水平翻转+主对角线翻转得到旋转后的二维矩阵。具体可以参考代码。
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]