题目: 矩阵置零

分析

方法一：暴力法

我们可以扫描整个矩阵，找到为 0 的元素，然后将其所在的行与列记录下来。再次扫描整个矩阵，将需要置为 0 的行与列进行置零。

时间复杂度：O(mn(m+n))，需要扫描两次矩阵。 空间复杂度：O(m+n)，需要使用两个数组来记录需要置为 0 的行与列。

Python 代码如下：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        row, col = [False] * m, [False] * n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = col[j] = True

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

方法二：使用标记

我们可以使用第一行与第一列来记录需要置为 0 的行与列，但是这样会造成一个问题，即第一行与第一列自身可能会有 0，所以需要使用额外的变量来记录第一行与第一列自身是否需要置为 0。接下来扫描除第一行与第一列之外的矩阵，将值为 0 的元素所在的行与列的第一个元素置为 0。最后再分别处理第一行与第一列即可。

时间复杂度：O(m*n)。 空间复杂度：O(1)。

Python 代码如下：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        flag_col0 = False

        for i in range(m):
            if matrix[i][0] == 0:
                flag_col0 = True
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0

        for i in range(m-1, -1, -1):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
            if flag_col0:
                matrix[i][0] = 0