LeetCode 73. 矩阵置零
目录
题目描述
✅ 73. 矩阵置零
题意分析
给定一个 $m \times n$ 的矩阵，只要某个位置的元素是 0，就把它所在的整行和整列全部置为 0，并且要求就地修改原矩阵，不返回新矩阵。
关键在于「触发置零的必须是原始的 0」。一旦边扫描边写 0，新写进去的 0 会被后面的扫描当成原始 0，从而引发连锁扩散，最终整个矩阵都变成 0。所以「先把要清的行列全部记下来，再统一执行」是绕不开的两阶段结构。
题目的进阶要求点明了空间预算：用 $O(mn)$ 的额外矩阵是显然做法，用两个长度分别为 $m$ 和 $n$ 的布尔数组是 $O(m + n)$ 的改进做法，而进阶要求的是只用常数额外空间，即 $O(1)$。这句话直接决定了解法形态——标记信息必须存回矩阵自身。
边界情况：矩阵只有一行或只有一列；
matrix[0][0]本身就是 0；整个矩阵没有 0；整个矩阵全是 0。
解法：第一行第一列原地标记
核心思路
难点不是“哪些位置要变成 0”，而是不能让新写入的 0 影响后续判断。因此流程必须分成两阶段：先记录原始 0 对应的行列，再统一置零。
常规做法用两个布尔数组记录行、列，空间为 $O(m+n)$。要做到 $O(1)$，可以直接借用矩阵的第一列记录“这一行是否清零”，借用第一行记录“这一列是否清零”。内部位置
(row, col)为 0 时，只写入matrix[row][0]和matrix[0][col]，暂不修改其他格子。
matrix[0][0]同时属于第一行和第一列，无法保存两个状态，所以额外用firstRowZero、firstColZero记录它们最初是否含 0。内部区域处理完后，再根据这两个变量清理第一行和第一列。循环不变量是：标记阶段结束后，对任意
row > 0，matrix[row][0] == 0表示第row行应清零；对任意col > 0，matrix[0][col] == 0表示第col列应清零。首行首列必须最后处理，否则会提前破坏这些标记。
解题步骤
- 扫描第一行和第一列，分别保存它们原本是否含 0。
- 扫描不含第一行、第一列的内部区域；遇到 0，就把对应的行标记和列标记置为 0。
- 根据第一列的行标记，清零内部各行。
- 根据第一行的列标记，清零内部各列。
- 根据
firstRowZero、firstColZero，最后清零第一行和第一列。例如
[[1,1,1],[1,0,1],[1,1,1]]：内部的 0 把matrix[1][0]、matrix[0][1]设为 0；第二阶段只清第 1 行和第 1 列，不会把新产生的 0 再次扩散。
代码实现
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean firstRowZero = false;
boolean firstColZero = false;
for (int col = 0; col < n; col++) {
firstRowZero |= matrix[0][col] == 0;
}
for (int row = 0; row < m; row++) {
firstColZero |= matrix[row][0] == 0;
}
for (int row = 1; row < m; row++) {
for (int col = 1; col < n; col++) {
if (matrix[row][col] == 0) {
matrix[row][0] = 0;
matrix[0][col] = 0;
}
}
}
for (int row = 1; row < m; row++) {
for (int col = 1; col < n; col++) {
if (matrix[row][0] == 0 || matrix[0][col] == 0) {
matrix[row][col] = 0;
}
}
}
if (firstRowZero) {
for (int col = 0; col < n; col++) {
matrix[0][col] = 0;
}
}
if (firstColZero) {
for (int row = 0; row < m; row++) {
matrix[row][0] = 0;
}
}
}
}
func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
firstRowZero, firstColZero := false, false
for col := 0; col < n; col++ {
firstRowZero = firstRowZero || matrix[0][col] == 0
}
for row := 0; row < m; row++ {
firstColZero = firstColZero || matrix[row][0] == 0
}
for row := 1; row < m; row++ {
for col := 1; col < n; col++ {
if matrix[row][col] == 0 {
matrix[row][0] = 0
matrix[0][col] = 0
}
}
}
for row := 1; row < m; row++ {
for col := 1; col < n; col++ {
if matrix[row][0] == 0 || matrix[0][col] == 0 {
matrix[row][col] = 0
}
}
}
if firstRowZero {
for col := 0; col < n; col++ {
matrix[0][col] = 0
}
}
if firstColZero {
for row := 0; row < m; row++ {
matrix[row][0] = 0
}
}
}
复杂度分析
- 时间复杂度：$O(mn)$，每个格子只被常数次访问。
- 空间复杂度：$O(1)$，标记复用第一行、第一列，只额外使用两个布尔变量。
关键点总结
- 先标记、后置零，避免新写入的 0 污染判断。
- 第一行和第一列就是原地版的行、列标记数组。
matrix[0][0]无法同时表达两个状态，因此需额外保存首行、首列信息。- 清理顺序必须是内部区域在前，第一行和第一列在后。
易错点总结
- 边扫描边清零会产生连锁扩散，例如中心为 0 的
3 × 3矩阵会被错误地全部清空。- 忘记单独记录第一行或第一列，会丢失它们原本是否需要清零的信息。
- 先清第一行、第一列会破坏标记，使内部位置漏清。
- 行列维度不要写反，非方阵最容易暴露这类错误。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 面试题 01.08. 零矩阵 | 中等 | 同题的原地标记复刻 |
| 289. 生命游戏 | 中等 | 原地状态编码避免污染 |
| 48. 旋转图像 | 中等 | 矩阵原地翻转与坐标映射 |
| 54. 螺旋矩阵 | 中等 | 四边界收缩遍历 |