48. 旋转图像

Problem: 48. 旋转图像

思路

思路一

用辅助数组的方式很好做
原矩阵的matrix[i][j] 对应于 反转后的 matrix[j][n - i - 1]
物理意义：对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 借助于辅助矩阵

        n = len(matrix)

        tem = copy.deepcopy(matrix) # 深拷贝

        for i in range(n):
            for j in range(n):
                matrix[j][n-i-1] = tem[i][j]
 

思路二

如果需要原地修改则需要观察，借用K神图片

可以发现A被覆盖掉了，所以可以用临时变量temp存储

原矩阵中的matrix[i][j]对应旋转后的matrix[j][n-1-i]
原矩阵中的matrix[j][n-1-i]对应旋转后的matrix[n-1-i][n-1-j]
原矩阵中的matrix[n-1-i][n-1-j]对应旋转后的matri[n-1-j][i]
原矩阵中的matri[n-1-j][i]对应旋转后的matrix[i][j]

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)

        for i in range(n // 2):
            for j in range((n + 1) // 2):
                tem = matrix[i][j]
                matrix[i][j] = matrix[n - j - 1][i]
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
                matrix[j][n - i - 1] = tem

思路三

通过观察可以得出：原矩阵可以通过一次「水平翻转」+「主对角线翻转」得到旋转后的二维矩阵。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
    
        # 顺时针旋转90° = 水平翻转 + 沿主对角线反转
        # 水平翻转
        n = len(matrix)
        for i in range(n // 2):
            matrix[i], matrix[n - 1 - i] = matrix[n - 1 - i], matrix[i]
        
        # 沿主对角线反转
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

解题方法

模拟

复杂度

时间复杂度: $O(n^2)$ 两重循环

空间复杂度: $O(1)$ 一个临时变量