力扣hot 100之矩阵四题解法总结

本期总结hot100 中二维矩阵的题，时空复杂度就不分析了

1.矩阵置零

原地标记，用第一行和第一列作为当前行列是否为0的标记，同时用两个标签分别记录0行、0列的标记空间中原本是否有0

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # inf, 0, >0分别指示新
        m, n = len(matrix), len(matrix[0])
        flag_fc, flag_fr = False, False
        for num in matrix[0]:
            if num == 0:
                flag_fr = True
                break
        for i in range(m):
            if matrix[i][0] == 0:
                flag_fc = True
                break
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        if flag_fc == True:
            for i in range(m):
                matrix[i][0] = 0
        
        if flag_fr == True:
            for i in range(n):
                matrix[0][i] = 0

2.螺旋矩阵

以四个状态标记当前移动的四个方向，当前移动的界限由其后一个方向已经转的圈数来界定，注意到状态3的前一个圈数为状态0，所以在状态2完成时要及时更新界限，否则状态3的界限会因晚更新而出错

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 用四个数对应4个遍历的方向[0, 1, 2, 3] - [右，下，左，上]
        m, n = len(matrix), len(matrix[0])
        done_number = 0
        ans = []
        now_state, c_r, i, j = 0, 0, 0, 0
        while done_number < (m * n):
            ans.append(matrix[i][j])
            done_number += 1
            if now_state == 0:
                if j < (n - 1 - c_r):
                    j += 1
                else:
                    now_state = 1
                    i += 1
            elif now_state == 1:
                if i < (m - 1 - c_r):
                    i += 1
                else:
                    now_state = 2
                    j -= 1
            elif now_state == 2:
                if j > c_r:
                    j -= 1
                else:
                    now_state = 3
                    i -= 1
                    c_r += 1
            else:
                if i > c_r:
                    i -= 1
                else:
                    # c_r += 1
                    now_state = 0
                    j += 1
            
        return ans

3.旋转图像

旋转图像，本题是对一个数组原地顺时针旋转90度

规律为

matrix[i][j]（原索引位置）​→matrix[j][n−1−i]（旋转后索引位置）

第一种​复制数组，不满足原地的要求

第二种设置个中间变量，四个为一组螺旋旋转，保存原先maxtrix[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 // 2 + (n % 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

4.搜索二维矩阵Ⅱ

对于这种数组，右上角元素的特点：在单行中最大，在单列中最小

由此可用当前右上角数与target比较，缩小范围，进行排除：如等于则找到；target大于右上角则行数减一（当前行必无target）、反之列数减一（当前列必无target）

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        cur_r, cur_u = len(matrix[0]) - 1, 0
        while cur_r >= 0 and cur_u <= (len(matrix) - 1):
            if matrix[cur_u][cur_r] == target:
                return True
            elif matrix[cur_u][cur_r] > target:
                cur_r -= 1
            else:
                cur_u += 1
        
        return False

思路参考各路题解，欢迎补充