题目描述
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
输入
m x n 的整数矩阵 matrix
输出
原地修改矩阵，将包含 0 的行和列全部置零
约束条件
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-2^31 <= matrix[i][j] <= 2^31 - 1
进阶约束
一个直观的解决方案是使用 的额外空间，但这并不是一个好的解决方案。一个简单的改进方案是使用 的额外空间，但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗？
示例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]]解题思路
这道题的难点在于一个”连锁反应”陷阱：你不能在遍历过程中直接把行和列置零，因为那些被置零的位置会在后续遍历中被误判为”原本就是 0”，从而错误地波及更多行和列——最终整个矩阵可能全变成 0。
💡 核心直觉：我们需要一种方式来”记住”哪些行和列需要被置零，而不是在遍历过程中立即执行。就像在纸质表格上做标记——先用铅笔圈出哪些行和列有 0，全部圈完后再统一擦除。
从暴力解法出发
最朴素的想法：深拷贝一份矩阵，遍历拷贝来找 0，在原矩阵上执行置零：
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) copy = [row[:] for row in matrix]
for i in range(m): for j in range(n): if copy[i][j] == 0: for k in range(n): matrix[i][k] = 0 # 整行置零 for k in range(m): matrix[k][j] = 0 # 整列置零- 时间复杂度：——每个 0 都要遍历整行 + 整列
- 空间复杂度：——完整副本
显然不可接受。
用两个数组记录零的位置（ 空间）
不复制矩阵，用两个布尔数组分别记录哪些行、哪些列包含 0：
class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: m, n = len(matrix), len(matrix[0]) zero_rows = [False] * m zero_cols = [False] * n
# 第一遍：记录 for i in range(m): for j in range(n): if matrix[i][j] == 0: zero_rows[i] = True zero_cols[j] = True
# 第二遍：执行 for i in range(m): for j in range(n): if zero_rows[i] or zero_cols[j]: matrix[i][j] = 0- 时间复杂度：
- 空间复杂度：
已经很好了，但题目进阶要求是 空间。数组本身有 个位置——能不能借用矩阵自己的一部分来充当标记数组？
原地标记：用第一行和第一列做”标记牌”（ 空间）
关键的洞察：只要 个布尔标记位就够了。矩阵的第一行（ 个元素）加上第一列（ 个元素）刚好够用！
🧠 直觉理解：把第一行当作”列标记牌”——
matrix[0][j] = 0表示”第 j 列需要清零”。把第一列当作”行标记牌”——matrix[i][0] = 0表示”第 i 行需要清零”。剩下的[1,m) × [1,n)区域是真正的”工作区”，我们遍历它、发现 0、在标记牌上记录。
但有个麻烦事：第一行和第一列既要是”标记牌”，自己本身也可能是数据——如果第一行原本就有 0，它在标记牌上的 0 到底代表”第一行需要清零”还是”某列需要清零”？
所以我们需要两个独立变量 r 和 c，提前记录第一行和第一列是否原本就含 0。
算法四步走
第一步：检查第一行和第一列
m, n = len(matrix), len(matrix[0])r = c = Falsefor i in range(n): if matrix[0][i] == 0: r = True # 第一行需要归零for i in range(m): if matrix[i][0] == 0: c = True # 第一列需要归零⚠️ 注意：
matrix[0][0]同时属于第一行和第一列。如果它是 0，r和c都会变成True，这是正确的——第一行和第一列都得清零。
第二步：遍历工作区，在标记牌上记录
遍历 [1, m) × [1, n)，遇到 0 就在第一行和第一列打标记：
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 列需要清零 → 刻在第一行第三步：根据标记牌，在工作区执行置零
再次遍历 [1, m) × [1, n)，看一行或一列是否被标记：
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💡 这里有一个巧妙的”自动继承”：如果第一行原本的某个
matrix[0][j]就是 0（比如示例 2 中的matrix[0][3]=0），它不需要我们在第二步额外标记，在第三步中会自然地让第 j 列的工作区被置零——因为matrix[0][j]这个位置本身就同时是数据也是标记。
第四步：处理第一行和第一列自己
最后才处理第一行和第一列——这必须在最后做，否则标记信息就丢了：
if r: for i in range(n): matrix[0][i] = 0if c: for i in range(m): matrix[i][0] = 0执行过程可视化
以示例 1 matrix = [[1,1,1],[1,0,1],[1,1,1]] 为例：
步骤 1：检查首行首列
- 第一行
[1,1,1]，无 0 →r = False - 第一列
[1,1,1]，无 0 →c = False
步骤 2：打标记（遍历 i=1,2 和 j=1,2）
i | j | matrix[i][j] | 操作 | 矩阵变化 |
|---|---|---|---|---|
| 1 | 1 | 0 | matrix[1][0]=0, matrix[0][1]=0 | [[1,**0**,1],[**0**,0,1],[1,1,1]] |
| 1 | 2 | 1 | 无操作 | 不变 |
| 2 | 1 | 1 | 无操作 | 不变 |
| 2 | 2 | 1 | 无操作 | 不变 |
标记完成后的矩阵：[[1,0,1],[0,0,1],[1,1,1]]
步骤 3：根据标记执行（遍历 i=1,2 和 j=1,2）
i | j | matrix[i][0] | matrix[0][j] | 条件满足？ | 操作 | 矩阵变化 |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 是 | 置零 | 已经是 0 |
| 1 | 2 | 0 | 1 | 是（matrix[1][0]=0） | 置零 | matrix[1][2]=0 |
| 2 | 1 | 1 | 0 | 是（matrix[0][1]=0） | 置零 | matrix[2][1]=0 |
| 2 | 2 | 1 | 1 | 否 | 不变 | 不变 |
步骤 4：处理首行首列
r = False→ 不动第一行c = False→ 不动第一列
最终结果：[[1,0,1],[0,0,0],[1,0,1]] ✅
再看示例 2 matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]（）：
步骤 1：检查首行首列
- 第一行
[0,1,2,0]，有 0 →r = True - 第一列
[0,3,1]，有 0 →c = True
步骤 2：打标记（遍历 i=1,2 和 j=1,2,3）
所有元素都非 0，不写入新标记。但注意——matrix[0][3] 原本就是 0，它作为”列 3 的标记”已经存在了！
步骤 3：根据标记执行（遍历 i=1,2 和 j=1,2,3）
i | j | matrix[i][0] | matrix[0][j] | 条件满足？ | 操作 |
|---|---|---|---|---|---|
| 1 | 1 | 3 | 1 | 否 | 不变 |
| 1 | 2 | 3 | 2 | 否 | 不变 |
| 1 | 3 | 3 | 0 | 是 | matrix[1][3]=0 |
| 2 | 1 | 1 | 1 | 否 | 不变 |
| 2 | 2 | 1 | 2 | 否 | 不变 |
| 2 | 3 | 1 | 0 | 是 | matrix[2][3]=0 |
步骤 4：处理首行首列
r = True→ 第一行全置零c = True→ 第一列全置零
最终结果：[[0,0,0,0],[0,4,5,0],[0,3,1,0]] ✅
💡 示例 2 中，
matrix[0][3]=0从未被步骤 2 刻意标记过——它天生就是标记。在步骤 3 中，任何工作区元素只要列号 j=3，就会发现matrix[0][3]=0，从而被正确置零。第一行中不在第一列的 0，天然充当了该列的标记——这也是为什么步骤 1 要先检查第一行并记录r：因为第一行自己的 0 既承担”这一列要清零”的标记职责，又承担”整行自身也需要清零”的数据职责。
复杂度
- 时间复杂度：。两遍遍历，每个元素被访问常数次。
- 空间复杂度：。只使用了两个布尔变量
r和c。
代码
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]) r = c = False for i in range(n): if matrix[0][i] == 0: r = True for i in range(m): if matrix[i][0] == 0: c = True for i in range(1, m): for j in range(1, n): if matrix[i][j] == 0: matrix[i][0] = matrix[0][j] = 0
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
if r: for i in range(n): matrix[0][i] = 0 if c: for i in range(m): matrix[i][0] = 0逐行解读：
r = c = False：两个布尔哨兵，记录第一行和第一列的”身世”——它们自己是否包含 0。- 检查第一行：遍历
matrix[0][i]，只要有一个 0，r就为True。 - 检查第一列：同理记录
c。 - 打标记：双重循环遍历工作区
[1,m) × [1,n)，matrix[i][0] = matrix[0][j] = 0利用 Python 的链式赋值，一步将行标记和列标记同时写入。 - 执行置零：再次遍历工作区，检查所在行的首元素或所在列的首元素是否为 0。
- 收尾第一行：如果
r为真，将整行清空。 - 收尾第一列：如果
c为真，将整列清空。
⚠️ 顺序至关重要：步骤 6 和 7 必须在步骤 4-5 之后。如果先清零第一行/列，标记信息就丢失了，工作区将无法正确判断哪些行列需要置零。
总结
「矩阵置零」教会我们一个经典的空间优化技巧：用输入数据的”边缘”做标记区。
🧠 核心收获：当需要 的标记空间而只有 的矩阵可用时，考虑把矩阵的第一行和第一列”征收”为标记数组。代价是额外用两个变量保存第一行和第一列自身的原始信息。这种”借用输入数据做辅助存储”的思路在算法设计中反复出现——当你被要求 空间却需要”记忆”某些信息时，问问自己：输入数组的某些位置能不能被复用？
同类题目推荐：
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时