LC73　矩阵置零¶

中等通过率 71.5%python3核心代码模式矩阵样例通过牛客 AC数组哈希表矩阵

一句话

借首行首列当标记位，把「哪些行列要清零」的记录压进矩阵自己。

解题思路¶

这题考什么¶

朴素做法的陷阱在于不能边扫边清：把某个 0 所在的行列就地刷成 0 之后，这些新写进去的 0 会被后面的扫描当成原始的 0，继续触发它们所在行列的清零，最后整个矩阵被染黑。所以必须先完整地记录要清哪些行、哪些列，再统一动手。

记录方式一路优化下来是三档：

O(m n)   复制一份原矩阵，照着原件判断
O(m + n) 两个布尔数组 row_zero[i] / col_zero[j]
O(1)     把这两个布尔数组**存进矩阵本身**

最后一档的观察是：如果 matrix[i][j] 是 0，那么第 i 行和第 j 列最终都会被清空，其中自然也包括 matrix[i][0] 和 matrix[0][j]。既然这两个格子横竖都要变成 0，干脆提前把它们置 0，当作「第 i 行要清」「第 j 列要清」的标记—— 不会丢失任何还需要的信息。于是首列充当 row_zero 数组，首行充当 col_zero 数组。

唯一的冲突是 matrix[0][0]：它同时属于首行和首列，一个格子担不了两个标记。解法是把首行、首列自身是否含 0 这两件事先单独存进两个布尔变量，整个流程结束后再按它们处理首行首列。两个布尔变量是常数空间，不破坏 O(1)。「用数据结构自己存元信息」这类原地技巧见序列与数组。

数据规模与复杂度¶

1 <= m, n <= 200，-2^31 <= matrix[i][j] <= 2^31 - 1。时间 O(m n)：四趟扫描，其中两趟只走首行首列。除两个布尔变量外空间 O(1)。规模最大 200 x 200 = 4e4 个格子，时间不是瓶颈；这题考的是空间与顺序。

坑在哪¶

首行首列自身的状态必须最先单独记下来。标记趟会把 matrix[i][0] 与 matrix[0][j] 写成 0，一旦先写了标记再回头看首行首列有没有 0，就分不清那个 0 是原本就有的、还是自己刚打上去的标记。样例 2 的 [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 首行就带两个 0，正好考这一点。
标记趟与清零趟都从下标 1 开始扫，不碰首行首列。若标记趟把 i = 0 也算进去， matrix[0][j] 为 0 时会去写 matrix[0][0]，污染首列的标记；若清零趟把 i = 0 算进去，首行会被自己的标记提前刷掉，后面读 matrix[0][j] 判断列标记时全是 0，整个矩阵被清空。
首行首列必须最后处理，而且要在内部格子全部清完之后。提前把首行刷成 0，内部清零趟再读 matrix[0][j] 就全是 0 了，同样导致全盘染黑。
两个标记的读取要用 or：matrix[i][0] == 0 or matrix[0][j] == 0。用 and 会变成「行和列都被标记才清」，漏掉绝大多数该清的格子。
首行与首列的处理互不影响，因为此时内部格子已经定稿，首行首列的值不再被任何人读取，两个 if 谁先谁后都行。
题面写的是 n == matrix[0].length，保证至少有一行一列，不必担心 matrix 为空；但 m 或 n 为 1 的退化情形要能走通—— 此时内部的 range(1, m) 或 range(1, n) 是空循环，全部工作由最后两个 if 完成，逻辑仍然正确。
返回值是 None，答案留在入参 matrix 里。签名的返回类型是 void，判题机调用完之后回头读第 0 个参数。任何形如 matrix = ... 的重新绑定都不会被判题机看见，必须原地写。
严格比对：置零结果唯一，没有多解。

样例复核¶

matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]，期望 [[0,0,0,0],[0,4,5,0],[0,3,1,0]]。 m = 3，n = 4。

预扫首行：matrix[0][0] 与 matrix[0][3] 是 0 -> first_row_zero = True
预扫首列：matrix[0][0] 是 0 -> first_col_zero = True
标记趟（i, j 都从 1 起）：内部 6 个格子 4 5 2 / 3 1 5 里没有 0，
                          一个标记也没打上，首行首列维持原样
清零趟：读 matrix[i][0] 与 matrix[0][j]。第 0 列的 matrix[1][0] = 3、
        matrix[2][0] = 1 都非 0，行标记都没亮；
        第 0 行的 matrix[0][1] = 1、matrix[0][2] = 2 非 0，
        matrix[0][3] = 0 亮着 -> 第 3 列的内部格子被清空
        此时矩阵变成 [[0,1,2,0],[3,4,5,0],[1,3,1,0]]
first_row_zero 为真 -> 首行整行清空
first_col_zero 为真 -> 首列整列清空
终态 [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

与样例一致。注意第 3 列的清空靠的是原本就在 matrix[0][3] 的那个 0 充当了列标记——这正是「首行首列自身的 0 既是数据又是标记」需要预先记录的原因。

参考实现¶

solutions/leetcode/LC73/sol.py
from typing import List, Optional


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m = len(matrix)
        n = len(matrix[0])
        # 首行首列自身的 0 既是数据、又将被当成标记位，必须**在打任何标记之前**
        # 单独记下来，否则事后分不清那个 0 是原有的还是自己写上去的
        first_row_zero = False
        for j in range(n):
            if matrix[0][j] == 0:
                first_row_zero = True
        first_col_zero = False
        for i in range(m):
            if matrix[i][0] == 0:
                first_col_zero = True
        # 标记趟：只扫内部（下标从 1 起），把「第 i 行要清」记在 matrix[i][0]，
        # 「第 j 列要清」记在 matrix[0][j]。这两个格子横竖都会被清成 0，
        # 提前置 0 不丢信息。i 从 0 起会去写 matrix[0][0]，污染首列的标记
        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
        # 清零趟：同样只动内部。行标记或列标记任一亮着就清，
        # 用 and 会变成「两个都亮才清」，漏掉绝大多数该清的格子
        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
        # 首行首列留到最后：它们此刻还兼着标记位，提前刷 0 会让上面的清零趟
        # 读到一片 0，把整个矩阵染黑。到这里内部已定稿，标记可以功成身退
        if first_row_zero:
            for j in range(n):
                matrix[0][j] = 0
        if first_col_zero:
            for i in range(m):
                matrix[i][0] = 0
        # 不返回任何东西：答案留在入参 matrix 里，判题机调用完之后回头读它

LC73 矩阵置零¶