Set Matrix Zeroes

Q: 将矩阵置零的时间复杂度是多少？

对于一个 m × n 矩阵，时间复杂度为 O(m·n)，因为每个单元格都会以常数次读写。没有更优的解法，因为任何被跳过的单元格都可能是会改变答案的 0。使用标记数组时，额外空间复杂度为 O(m + n)；使用第一行和第一列作为标记时，额外空间复杂度为 O(1)。

中等数组和字符串哈希

+10

输入是一个 m × n 的整数网格，按行给出，因此 matrix[i][j] 位于第 i 行、第 j 列。无论网格中的哪个位置有 0，都要将该整行和整列设为 0。只有一开始就存在的 0 才算数：你将某个单元格改为 0 后，它所在的行和列不会因此被清零。你可以直接修改网格，并返回它。

函数

setZeroes(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: 整数网格，每行对应一个内部列表
返回值integer-2d-array: 将所有包含 0 的行和列都设为 0 的矩阵

约束条件

m == matrix.length 并且 n == matrix[i].length
1 ≤ m, n ≤ 1000 并且 m × n ≤ 5000
所有 m 行都包含 n 个值。
-1000 ≤ matrix[i][j] ≤ 1000

示例

输入: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
输出: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
解释: 唯一的 0 位于第 1 行、第 1 列。第 1 行全部变为 0，第 1 列也全部变为 0，因此 8 和 6 都变成了 0。四个角都不在这两行中，因此保留原值。

进阶

下面的最佳方法会保留两个额外的布尔值。你能只用一个吗？让 matrix[0][0] 表示第一行。

题解

你写入的 0 和给定的 0 看起来完全一样，所以在扫描过程中清除行会让 0 扩散到矩阵中。将读取和写入分开：先记录哪些行和列中原本有 0，再清除它们。用两个数组保存这些记录；或者，为了将额外空间控制在 O(1)，使用矩阵自身的第一行和第一列。

在两个数组中标记行和列

思路

当单元格所在的行或列在开始时有一个 0 时，该单元格最终会变成 0。因此，先遍历一遍，只读取数据，不写入数据，记录两组信息：zeroRow[i] 和 zeroCol[j]，然后将所在行或列已标记的每个单元格清零。这样不会出现连锁影响，因为所有读取都在首次写入之前完成。

每次遍历都会访问 m·n 个单元格一次，因此时间复杂度为 O(m·n)，数组中存放 m + n 个布尔值。

算法

创建一个包含 m 个元素的 zeroRow 和一个包含 n 个元素的 zeroCol，所有元素都设为 false。
扫描每个单元格。当 matrix[i][j] 为 0 时，将 zeroRow[i] 和 zeroCol[j] 设为 true。
再次扫描每个单元格，如果 zeroRow[i] 或 zeroCol[j] 为 true，就将该单元格设为 0。
返回矩阵。

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_row = [False] * m
    zero_col = [False] * n
    # Pass 1: only read, so a new zero can never spread further.
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_row[i] = True
                zero_col[j] = True
    # Pass 2: write.
    for i in range(m):
        for j in range(n):
            if zero_row[i] or zero_col[j]:
                matrix[i][j] = 0
    return matrix

将第一行和第一列用作标记

思路

第一列每行有一个单元格，第一行每列有一个单元格，这正好对应两个标记数组的形状。因此，行 i、列 j 上的 0 会将 0 写入 matrix[i][0] 和 matrix[0][j]。这样不会丢失任何信息：这些单元格都位于本来就必须变成 0 的行或列中。

第 0 行和第 0 列既存放数据，也用作标记；在它们上面设置标记，会让你无法判断它们原本是否包含 0。因此，先检查它们，并用两个布尔值保存结果。只标记并填充满足 i ≥ 1 和 j ≥ 1 的单元格，最后再清空第 0 行和第 0 列，因为填充时会读取它们。

在第二个示例中，行 1、列 1 上的 3 会保留下来，因为它的标记 matrix[1][0] = 9 和 matrix[0][1] = 4 都不是 0。时间复杂度仍为 O(m·n)，额外内存只需两个布尔值（在 R 中为 O(m·n)，因为 R 会先复制输入）。

算法

如果第 0 行中有 0，就设置 firstRowZero；如果第 0 列中有 0，就设置 firstColZero。
对于每个满足 i ≥ 1 且 j ≥ 1 的单元格，如果其中的值为 0，就将 matrix[i][0] 和 matrix[0][j] 设置为 0。
对于每个满足 i ≥ 1 且 j ≥ 1 的单元格，如果 matrix[i][0] 或 matrix[0][j] 为 0，就将该单元格设置为 0。
如果 firstRowZero 为真，就将第 0 行设置为 0。如果 firstColZero 为真，就将第 0 列设置为 0。
返回矩阵。

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    # The first row and column will hold the markers, so remember first
    # whether they need to become zero themselves.
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    # Mark: a zero inside the matrix flags its row in column 0
    # and its column in row 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
    # Fill the inside from the markers.
    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
    # The marker row and column go last.
    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
    return matrix

易错点和边界情况

一找到 0 就清空对应的行和列。在第一个例子中，新出现的 0 位于第 1 行、第 2 列，接着第 2 列也被清空，最后只剩下左上角的 3。
让 matrix[0][0] 同时标记第 0 行和第 0 列。在 [[1, 2, 3], [0, 5, 6], [7, 8, 9]] 中，第 0 列里的 0 会错误地清空第 0 行。
填充之前就清空第 0 行或第 0 列。在 [[0, 2, 3], [4, 5, 6], [7, 8, 9]] 中，所有列看起来都会被标记，整个矩阵就会变成 0。
忘记处理只有一行或一列的情况。只有一行时，从 1 开始的循环不会执行任何操作，所有工作都由布尔值完成：[[1, 0, 3]] 必须变成 [[0, 0, 0]]。

常见问题3

为什么不能在扫描矩阵的同时把这些位置设为 0？

你写入的 0 看起来和原来的 0 一样。扫描到它时，它会清空所在的行和列，这些新产生的 0 还会继续扩散。更改任何单元格之前，先记录所有原来的 0。

将矩阵置零的时间复杂度是多少？

对于一个 m × n 矩阵，时间复杂度为 O(m·n)，因为每个单元格都会以常数次读写。没有更优的解法，因为任何被跳过的单元格都可能是会改变答案的 0。使用标记数组时，额外空间复杂度为 O(m + n)；使用第一行和第一列作为标记时，额外空间复杂度为 O(1)。

你能用一个特殊值标记单元格，而不是用 0 吗？

有些答案会在需要清除的单元格中写入占位符，并在最后将占位符转换为 0。只有当占位符绝不会出现在输入中时，这种方法才有效，而整数矩阵通常无法保证这一点。对于每个 0，都沿着对应的行和列写入占位符，还会导致时间复杂度达到 O(m·n·(m + n))。

def setZeroes(matrix):
    # 在这里编写代码

测试 #1

测试 #2

参数

matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]

预期输出

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]