旋转图象

1、题目

图1

2、题解

辅助存储

根据旋转示意不难看出：

• 原矩阵第i行元素旋转到第n-1-i列
• 原矩阵第j列元素旋转到第j行

该方法存在问题：写入一个元素后，原矩阵的元素会被覆盖，导致被覆盖的元素无法写入到旋转后的位置，所以需要一个辅助矩阵进行元素存储。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        tmp = [[matrix[r][c] for c in range(col)]for r in range(row)]

        for i in range(row):
            for j in range(col):
                matrix[i][j] = tmp[row-1-j][i]

上述方法需要遍历所有元素以及创建新的辅助矩阵，因此时间复杂度和空间复杂度都是\(N^2\)

原地修改

以矩阵四个角的元素为例，从左上角开始顺时针元素一次为A,B,C,D,旋转90°等价于依次执行\(D\to A,A\to B,B\to C,C\to D\)。第一次覆盖会让A元素丢失，需要一个tmp预先存储A，旋转的操作就变为\(A\leftarrow D\leftarrow C\leftarrow B\leftarrow tmp\)。

从循环流程来看，当矩阵大小\(n\)为偶数时，取前\(\frac{n}2\)行、前\(\frac{n}2\)列的元素为起始点；当矩阵大小n为奇数时，取前\(\frac{n}2\)行、前\(\frac{n+1}2\)列的元素为起始点。最后再结合上一个方法的旋转公式。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range((n + 1) // 2):
                tmp = 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] = tmp