73. 矩阵置零（Set Matrix Zeroes）
频次 ★★★ · 难度 🟡 · 高频：百度
题目
给定一个 m × n 的矩阵，如果某个元素为 0，则将其所在的行和列的所有元素都设为 0。必须原地修改。
示例：
输入: [[1,1,1],[1,0,1],[1,1,1]]
输出: [[1,0,1],[0,0,0],[1,0,1]]
思路
利用第一行和第一列作为标记：
- 先用两个变量记录第一行和第一列是否需要置零
- 遍历除第一行第一列外的区域，如果
matrix[i][j] == 0，标记matrix[i][0] = 0和matrix[0][j] = 0 - 根据第一行和第一列的标记来置零内部区域
- 最后处理第一行和第一列本身
这样空间复杂度从 O(m+n) 降到 O(1)。
代码
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean firstRowZero = false, firstColZero = false;
// 检查第一行和第一列
for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true;
// 用第一行和第一列做标记
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 根据标记置零
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 处理第一行和第一列
if (firstRowZero) for (int j = 0; j < n; j++) matrix[0][j] = 0;
if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0;
}复杂度
- 时间：O(m × n) — 遍历矩阵
- 空间：O(1) — 只用两个布尔变量
边界条件
- 矩阵中没有 0：
firstRowZero、firstColZero都为 false，标记阶段不写入任何 0，最终矩阵不变。 - 只有第一行/第一列含 0：靠
firstRowZero/firstColZero这两个独立变量记录，不会和”用第一行/第一列本身做标记”的逻辑冲突（这也是需要额外两个布尔变量、不能只用第一行第一列自己表示自己是否要清零的原因）。 matrix[0][0] == 0：会同时影响firstRowZero和firstColZero的判断（因为它既属于第一行也属于第一列），两个检查循环都会各自正确捕捉到。
变式
- 允许 O(m+n) 额外空间：用两个布尔数组分别记录哪些行、哪些列需要置零，思路更直观，是这道题的”简化版”，面试官通常会先问这个版本，再追问能不能优化到 O(1)。
- 类似”标记后统一处理”的技巧还能用在生命游戏（LeetCode 289 题）等需要”原地修改但不能影响后续判断”的场景。
易错点
- 检查第一行、第一列是否需要清零必须在开始标记之前做（用独立变量记录），因为标记阶段会把第一行第一列当作”标记位”覆写，如果标记完再检查就分不清哪些 0 是原来就有的、哪些是标记写上去的。
- 最后处理第一行、第一列本身，必须放在最后（先处理完内部区域），如果提前清零第一行/第一列，会丢失内部区域判断所需要的标记信息。
面试追问
- 为什么要用第一行第一列做标记，而不是直接开两个新数组？ 用第一行第一列复用存储空间可以把额外空间从 O(m+n) 降到 O(1)，这是面试官考察”能不能进一步压缩空间”的常见追问点，体现了”原地复用已有存储”的通用思路。
- 这个技巧的核心限制是什么？ 只适用于”可以牺牲部分原始数据（这里是第一行第一列的原值）来存储标记信息，并且后续能通过其他方式恢复所需信息”的场景；如果矩阵内容之后还需要精确保留第一行第一列的原始值用于别的用途，这个技巧就不适用了。
关联题
- 同套路：41. 缺失的第一个正数、448. 找到所有数组中消失的数字 —— 都是”借已有存储当标记位”省掉额外空间
- 易混：48. 旋转图像、54. 螺旋矩阵 —— 同为矩阵题，本题考标记复用，它们考坐标变换/边界收缩