73. 矩阵置零

题目链接：73. 矩阵置零

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

核心思考：常数空间的原地标记

如果申请一个等大的矩阵，空间复杂度是 $O(mn)$。如果申请两个数组分别记录哪些行哪些列该置零，空间复杂度是 $O(m+n)$。本题的最优解法是利用矩阵的第一行和第一列作为“记录板”，将空间复杂度压低到 $O(1)$。

1. 处理冲突点：因为第一行和第一列共享 matrix[0][0] 这个点，为了区分第一行原本是否有 0 和第一列原本是否有 0，我们需要使用两个额外的布尔标志位 row0_flag 和 col0_flag 单独记录第一行/第一列的初始状态。
2. 打标（Marking）：遍历矩阵中除首行首列外的所有元素。如果 matrix[i][j] == 0，则将它对应的“行首”和“列首”元素置零：matrix[i][0] = 0 和 matrix[0][j] = 0。
3. 根据记录板置零：再次遍历除首行首列外的元素。如果一个元素的行首或列首为 0，则该元素置零。
4. 清理首行首列：最后根据最开始存好的 row0_flag 和 col0_flag 来决定是否将第一行和第一列全部置零。

解题思路 (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])
        row0_flag = False
        col0_flag = False
        
        # 1. 记录第一行和第一列是否本身包含 0
        for j in range(n):
            if matrix[0][j] == 0:
                row0_flag = True
                break
        for i in range(m):
            if matrix[i][0] == 0:
                col0_flag = True
                break
                
        # 2. 利用第一行和第一列充当标记位，记录剩余部分的 0
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
                    
        # 3. 根据标记位，将其余部分置零
        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
                    
        # 4. 最后处理第一行和第一列本身
        if row0_flag:
            for j in range(n):
                matrix[0][j] = 0
        if col0_flag:
            for i in range(m):
                matrix[i][0] = 0

复杂度分析

• 时间复杂度：$O(M \times N)$，其中 $M$ 是行数，$N$ 是列数。我们对矩阵进行了三次有限次数的完整或部分扫描。
• 空间复杂度：$O(1)$。我们直接在原矩阵上复用空间进行标记，仅使用了常数个布尔变量。