零矩阵

题目

编写一种算法，若M×N矩阵中某个元素为0，则将其所在的行与列清零。

思路

暴力法，需要注意二维数组切片是浅拷贝，需要利用copy.deepcopy进行深拷贝。

class Solution:
    import copy
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rows, cols = len(matrix), len(matrix[0])
        help_matrix = copy.deepcopy(matrix)
        for row in range(rows):
            for col in range(cols):
                if help_matrix[row][col] == 0:
                    # 所在行，所在列全部置为0
                    matrix[row] = [0 for _ in range(cols)]
                    for j in range(rows):
                        matrix[j][col] = 0

时间复杂度：O(n^2)，两层循环
空间复杂度：O(n)，深拷贝了一个额外的数组

更优雅的解法，减少重复置为0的操作。
第一次遍历matrix，记录哪一行和哪一列有0；
第二次遍历，将行有0的这一列全部置为0，将列有0的这一行全部置为0.

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row=set()
        column=set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==0:
                    row.add(i)
                    column.add(j)
        for i in row:
            for j in range(len(matrix[0])):
                matrix[i][j]=0
        for j in column:
            for i in range(len(matrix)):
                matrix[i][j]=0