73. 矩阵置零 (Medium)
专题归类： 矩阵 LeetCode 链接： https://leetcode.cn/problems/set-matrix-zeroes/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个 m x n 的矩阵，如果某个元素为 0，则将其所在行和列的所有元素都设为 0。请原地操作。
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：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 == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1- 原地操作意味着不能使用额外的矩阵副本
题目详细分析
数据范围分析：
- 矩阵最大 200×200 = 40,000 个元素，暴力算法 O(m×n×(m+n)) 约 1.6×10^7 还可以接受，但显然 O(m×n) 才是标准解法。
- 元素值范围很大（32 位有符号整数），但题目只关心值是否为 0。
输入输出特征：
- 输入是二维矩阵，需要原地修改。
- 如果
matrix[i][j] == 0，那么第 i 行和第 j 列的所有元素都变为 0。
边界条件：
- 矩阵中只有一个 0 → 该行和该列全部置零。
- 矩阵中没有 0 → 矩阵不变。
- 矩阵只有一行或一列。
- 多个 0 的行列重叠 → 标为 0 的区域可能很大，但处理方式相同。
- 第一行或第一列本身包含 0 → 需要特殊处理，因为它们被用作标记后会被覆盖。
隐藏条件：
- “原地”意味着不能新建一个矩阵副本。
- 关键在于”标记”和”置零”两个阶段要分开：不能边标记边置零，否则会错误传播。
- 用第一行和第一列作为标记行/列是一种节省空间的技巧，但需要额外处理第一行和第一列本身。
小白版直白理解
想象有一个棋牌室，里面摆了很多张桌子（矩阵）。突然有人发现某张桌子上有垃圾（0 值），于是工作人员决定：所有和这张桌子同行、同列的桌子都要被清理掉。
但如果一路清理下去，可能会把原本没垃圾的桌子也标记为”已清理”，导致混乱——一个桌子被清理后，其他同行列的桌子可能本来不用清理，但现在也被牵连了。
聪明的办法：
- 先拿第一排和第一列的桌子做”备忘录”——如果某行有垃圾，就在这行的第一个桌子上写个记号；如果某列有垃圾，就在这列的第一个桌子上写个记号。
- 然后根据备忘录，把对应行和列的桌子都清理掉。
- 最后单独处理第一排和第一列的桌子——因为之前可能就有垃圾。
这样做的好处是：不需要额外的小本本，直接用现有的桌子当备忘录。
解题思路
思路一：使用第一行和第一列作为标记（推荐，O(1) 空间）
核心洞察：
我们需要知道哪些行和哪些列需要置零。如果直接用额外数组存储：
- 行标记数组：O(m) 空间
- 列标记数组：O(n) 空间
但我们可以利用矩阵本身的第一行和第一列来存储这些标记——因为不管第一行和第一列是否被置零，它们最终都会被处理。
关键步骤：
- 检查第一行和第一列本身是否有 0（备份）
- 遍历除第一行第一列外的区域，如果遇到 0，在对应的行首和列首标记 0
- 根据标记，将对应行和列（除第一行第一列外）置零
- 最后根据备份，处理第一行和第一列本身
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
# Step 1: 检查第一行和第一列是否包含 0
first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))
# Step 2: 用第一行和第一列标记需要置零的行和列
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0 # 标记第 i 行需要置零
matrix[0][j] = 0 # 标记第 j 列需要置零
# Step 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
# Step 4: 处理第一行和第一列本身
if first_row_has_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_has_zero:
for i in range(m):
matrix[i][0] = 0复杂度： O(m × n) 时间，O(1) 空间。
思路二：用额外标记数组（更易理解，O(m+n) 空间）
用两个布尔数组 row_zero 和 col_zero 分别记录哪些行和列需要置零。先扫描矩阵做标记，再根据标记置零。
def setZeroes_extraSpace(matrix):
m, n = len(matrix), len(matrix[0])
row_zero = [False] * m
col_zero = [False] * n
# Step 1: 标记需要置零的行和列
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row_zero[i] = True
col_zero[j] = True
# Step 2: 根据标记置零
for i in range(m):
for j in range(n):
if row_zero[i] or col_zero[j]:
matrix[i][j] = 0复杂度： O(m × n) 时间，O(m + n) 空间。
思路三：用一个标记变量（进阶优化）
第一次优化：可以用第一行和第一列作为标记数组，但只需要一个额外变量来记录第一列是否有 0（第一行是否有 0 用 matrix[0][0] 本身记录）。
def setZeroes_oneVar(matrix):
m, n = len(matrix), len(matrix[0])
col0 = False # 标记第一列是否有 0
# Step 1: 标记
for i in range(m):
if matrix[i][0] == 0:
col0 = True
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Step 2: 置零（从下往上处理，避免覆盖标记）
for i in range(m - 1, -1, -1):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if col0:
matrix[i][0] = 0注意： 这里从下往上遍历很重要，这样不会过早覆盖第一行的标记。
易错点
- 边标记边置零：如果在扫描时发现 0 就立即置零整行整列，会导致原本不是 0 的位置变成 0，从而错误地触发更多行/列置零（雪崩效应）。标记和置零必须分两步。
- 第一行列覆盖问题：用第一行和第一列做标记后，它们本身的信息会被覆盖。所以必须提前备份第一行和第一列是否有 0。
- 遍历顺序：在思路三中，从下往上遍历防止覆盖第一行的标记。
- 标记位置：标记时
matrix[i][0] = 0和matrix[0][j] = 0，不要搞反了：行标记在第一列、列标记在第一行。 - 索引范围：
matrix[i][0]是第 i 行的第一个元素（标记该行），matrix[0][j]是第 j 列的第一个元素（标记该列）。 - 只有一个 0 的情况：工作正常，但要注意标记是否被正确传递。
框架提炼
矩阵原地标记通用模板（利用首行列做标记）：
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
# Step 1: 备份首行首列的原始状态
first_row_flag = any(matrix[0][j] == 0 for j in range(n))
first_col_flag = any(matrix[i][0] == 0 for i in range(m))
# Step 2: 用首行首列标记其他区域
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 条件:
matrix[i][0] = 标记 # 标记行
matrix[0][j] = 标记 # 标记列
# Step 3: 根据标记修改其他区域
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 标记 or matrix[0][j] == 标记:
matrix[i][j] = 修改值
# Step 4: 处理首行首列
if first_row_flag:
for j in range(n):
matrix[0][j] = 修改值
if first_col_flag:
for i in range(m):
matrix[i][0] = 修改值这类问题的核心思路： 用一个额外的”标记层”（可以是额外数组，也可以是矩阵本身的行/列）来记录哪些行/列需要修改，然后再统一执行修改。关键在于标记和修改分离。