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)$。我们直接在原矩阵上复用空间进行标记，仅使用了常数个布尔变量。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

import sys

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

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.setZeroes(matrix)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py