73.矩阵置零

·题目描述

·解题思路

——————初步思路，暴力求解——————

1.遍历原矩阵，记录0位置的行列值，存入数组flags中，作为标志

2.读取flags中的元素，获取要置为0的行列值，然后两个循环将matrix中的对应元素置为0

代码：

    def setZeroes(self, matrix):
        #时间复杂度O（mn^2),空间复杂度o（mn）
        row = len(matrix)
        col = len(matrix[0])
        flags = []

        for i in range(row):
            for j in range(col):
                if matrix[i][j] == 0:
                    res = [i,j]
                    flags.append(res)

        for flag in flags:
            r,c = flag[0],flag[1]
            for i in range(row):
                matrix[i][c] =0
            for j in range(col):
                matrix[r][j] = 0

        return matrix

——————改进优化，使用哈希表——————

1.将原始需要记录行列的数组flags改为两个哈希表row和col

2.遍历矩阵将0位子的行列分别存入哈希表中

3.循环置为0

代码：

    def setZeroes(self, matrix):
          # 时间复杂度O(mn) 空间复杂度O(m+n)
        row_num = len(matrix)
        col_num = len(matrix[0]) if row_num > 0 else 0
        row = set()
        col = set()


        for i in range(row_num):
            for j in range(col_num):
                if matrix[i][j] == 0:
                    row.add(i)
                    col.add(j)

        for i in range(row_num):
            for j in range(col_num):
                if i in row or j in col:
                    matrix[i][j] = 0

        return matrix