力扣hot100之矩阵四题解法总结

本期总结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

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