11、旋转图像

题目描述

方法1、使用辅助数组

思路：找规律。发现第i行第j列数，旋转之后到达第j行倒数第i列。得到等式：$m[j][l-i-1]=m[i][j]$

时间复杂度：O(n^2^)。n为矩阵边长。

空间复杂度：O(n^2^)。需要构造辅助数组。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # m = copy.deepcopy(matrix)  # 深拷贝，改变新m不会导致同时改变原matrix
        l = len(matrix)
        m = [[0]*l for _ in range(l)]
        for i in range(l-1,-1,-1):
            for j in range(0,l):  # 正向遍历
                m[j][l-1-i] = matrix[i][j]  # 找规律，第i行第j列的数正好转到了第j行倒数第i列
        matrix[:] = m

方法2、原地旋转

思路：观察关键等式：$m[j][l-i-1]=m[i][j]$，不断的旋转，得到

从下旋转到上，发现四个等式一循环。

$m[i][j]=m[l-j-1][i]$

$m[l-j-1][i]=m[l-i-1][l-j-1]$

$m[l-i-1][l-j-1]=m[j][l-i-1]$

$m[j][l-i-1]=m[i][j]$

时间复杂度：O(n^2^)。遍历$[n/2]*[(n+1)/2]=O(n^2)$

空间复杂度：O(1)。

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):
                matrix[i][j], matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1] = matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1], matrix[i][j]

方法3、解压、逆序取值

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 解压，相当于转置；然后每行逆序取值。
        matrix[:] = list(zip(*matrix))
        for i in range(len(matrix)):
            matrix[i] = matrix[i][::-1]

示例：

>>>a = [1,2,3]
>>> b = [4,5,6]
>>> zipped = zip(a,b)     # 打包为元组的列表
[(1, 4), (2, 5), (3, 6)]
>>> zip(*zipped)          # *zipped 可理解为解压，返回二维矩阵式
[(1, 2, 3), (4, 5, 6)]

[::-1] 顺序相反操作，逆序取值

a='python'
b=a[::-1]
print(b) #nohtyp

方法4、水平翻转，对角线翻转

思路：水平翻转：$m[n-i-1][j]=m[i][j]$

主对角线翻转：$m[j][i]=m[i][j]$

联立方程正好为关键等式：$m[j][n-i-1]=m[i][j]$

时间复杂度：O(n^2^)。每次翻转需要遍历一半的数。

空间复杂度：O(1)。

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):
                matrix[n-i-1][j], matrix[i][j] = matrix[i][j], matrix[n-i-1][j]
        # 主对角线翻转
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]