73 Set Matrix Zeroes

题目

Set Matrix Zeroes

题解

首先需要注意，我们不能在扫描完整个矩阵之前进行清零操作，因为这样会把后面未扫描到的矩阵元素置零，从而可能导致零值被错误地扩散出去。

在空间复杂度必须为\(O(1)\)的限制下，我们只能在矩阵内存储需要清零的行/列信息。一个方法是在首行首列存储需要清零的行和列，但是这样会导致首行首列本身是否需要清零的信息被映射到同一个位置matrix[0][0]而无法区别开来，所以我们需要两个额外的变量来存储这两项信息。

代码

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row_size = len(matrix)
        column_size = len(matrix[0])

        first_row_has_0 = any([True for x in matrix[0] if x == 0])
        first_column_has_0 = any(
            [True for row in range(row_size) if matrix[row][0] == 0]
        )

        for row, array in enumerate(matrix):
            for column, value in enumerate(array):
                if value == 0:
                    matrix[row][0] = 0
                    matrix[0][column] = 0

        for row in range(1, row_size):
            if matrix[row][0] == 0:
                matrix[row] = [0] * column_size

        for column in range(1, column_size):
            if matrix[0][column] == 0:
                for row in range(row_size):
                    matrix[row][column] = 0

        if first_row_has_0:
            matrix[0] = [0] * column_size
        if first_column_has_0:
            for row in range(row_size):
                matrix[row][0] = 0