yicong@algo:~/code/06-matrix$ cat 0073-set-matrix-zeroes.cpp
73. 矩阵置零
// 思路
朴素做法:先扫一遍记下"所有含 0 的行号"和"所有含 0 的列号", 再扫一遍把命中的行列整体置 0。用两个布尔数组,额外空间 O(m + n)。 进阶要求是 O(1) 额外空间。做法是把那两个布尔数组"塞进矩阵自己身上"—— 拿第一行当"列标记",第一列当"行标记": matrix[i][0] == 0 ⇒ 第 i 行要被清零 matrix[0][j] == 0 ⇒ 第 j 列要被清零 这样标记位不占额外空间,代价是第一行和第一列"既是数据又是标记",会互相污染。 于是必须在动手之前用两个 bool 变量,单独记下第一行、第一列原本有没有 0: firstRowHasZero —— 第一行原本含 0 吗 firstColHasZero —— 第一列原本含 0 吗 为什么要单独记:matrix[0][0] 这一个格子里塞不下两条信息, 它无论是 0 还是非 0,都分不清到底是"第一行有 0"还是"第一列有 0", 甚至可能两者都有。所以必须外挂两个 bool 来消歧。 版本二(正解)四步走: ① 用两个 bool 记下第一行、第一列原本是否含 0 ② 从 (1,1) 开始扫,遇到 0 就把 matrix[i][0] 和 matrix[0][j] 置 0(打标记) ③ 从 (1,1) 开始扫,只要所在行或所在列的标记是 0,就把自己置 0 ④ 最后按两个 bool 决定要不要把第一行 / 第一列整体清零 ④ 必须在 ③ 之后:标记位就存在第一行和第一列里,先清就没标记可用了。
// 时间复杂度
O(m·n)。四趟扫描,每趟遍历 O(m·n) 个格子。
// 空间复杂度
版本一:O(m + n),两个布尔数组 版本二:O(1),只有两个 bool 变量,标记位借用了矩阵自身
// 易错点
1. 第一行、第一列必须先用两个 bool 单独记下来,不能只凭 matrix[0][0] 判断。 一个格子里装不下"第一行有 0"和"第一列有 0"两条信息,它们的组合有四种情况, 而 matrix[0][0] 只有 0 / 非 0 两种状态。 2. 第四步(处理第一行/第一列自己)必须放在第三步之后。 标记位存在第一行和第一列里,先清零就把标记擦掉了。 3. 第②步和第③步都要从 (1,1) 开始,跳过第一行第一列——它们单独处理。 从 (0,0) 开始会把标记位自己当成数据置零,连带污染。 4. 第③步的判断是"或"不是"与": matrix[i][0] == 0 || matrix[0][j] == 0 写成 && 的话,只有行列都被标记才清,绝大多数该清的清不掉。 5. rows == 0 要提前返回。matrix[0] 只有在矩阵非空时才安全。
// 面试口述要点
1. 先给 O(m+n) 空间的做法:两个布尔数组记行列,一遍标记、一遍置零; 2. 再说怎么压到 O(1):标记信息可以复用矩阵的第一行和第一列; 3. 重点讲清为什么需要两个额外的 bool——matrix[0][0] 一个格子放不下两条信息; 4. 最后强调执行顺序:先标记、再清内部、最后清第一行第一列,顺序反了标记就丢了; 5. 复杂度:时间 O(m·n)(四趟线性扫描),空间 O(1)。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// ================================================================
// 版本一:两个布尔数组,额外空间 O(m + n),最直观
// ================================================================
void setZeroes_v1(vector<vector<int>>& matrix) {
int rows = (int)matrix.size();
if (rows == 0) {
return;
}
int cols = (int)matrix[0].size();
vector<bool> rowHasZero(rows, false); // 第 i 行要不要清零
vector<bool> colHasZero(cols, false); // 第 j 列要不要清零
// 第一遍:只做标记,不改矩阵
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
rowHasZero[i] = true;
colHasZero[j] = true;
}
}
}
// 第二遍:按标记统一清零
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (rowHasZero[i] || colHasZero[j]) {
matrix[i][j] = 0;
}
}
}
}
// ================================================================
// 版本二:借用第一行、第一列当标记位,额外空间 O(1)(正解)
// ================================================================
void setZeroes(vector<vector<int>>& matrix) {
int rows = (int)matrix.size();
if (rows == 0) {
return;
}
int cols = (int)matrix[0].size();
// ---------- 第 ① 步:先单独记下第一行、第一列原本有没有 0 ----------
// 这一步是整个算法的地基。不能省,也不能用 matrix[0][0] 代替:
// 一个格子里装不下"第一行有 0"和"第一列有 0"这两条独立信息。
bool firstRowHasZero = false;
bool firstColHasZero = false;
for (int j = 0; j < cols; j++) {
if (matrix[0][j] == 0) {
firstRowHasZero = true;
break;
}
}
for (int i = 0; i < rows; i++) {
if (matrix[i][0] == 0) {
firstColHasZero = true;
break;
}
}
// ---------- 第 ② 步:从 (1,1) 开始打标记 ----------
// 遇到 0 就在它所在行的行首、所在列的列首各打一个 0
// 注意从 (1,1) 起,跳过第一行第一列——它们是标记区,不是数据区
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0; // 标记:第 i 行要清零
matrix[0][j] = 0; // 标记:第 j 列要清零
}
}
}
// ---------- 第 ③ 步:按标记把内部数据清零 ----------
// 判断是"或":只要所在行或所在列被标记了,自己就要变 0
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// ---------- 第 ④ 步:最后处理第一行和第一列自己 ----------
// 必须放在第③步之后。标记位就存在第一行、第一列里,
// 先清零就把标记擦掉了,第③步会全部失效。
if (firstRowHasZero) {
for (int j = 0; j < cols; j++) {
matrix[0][j] = 0;
}
}
if (firstColHasZero) {
for (int i = 0; i < rows; i++) {
matrix[i][0] = 0;
}
}
}
};
// 本地测试:先读行数 r、列数 c,再读 r*c 个元素(按行);输出置零后的矩阵
// 同时跑两个版本并比对结果,版本一思路更直白,适合当版本二的对照
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int r, c;
if (!(cin >> r >> c)) return 0;
vector<vector<int>> matrix(r, vector<int>(c));
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
cin >> matrix[i][j];
vector<vector<int>> copy = matrix; // 两版都是原地修改,各用一份
Solution().setZeroes_v1(matrix);
Solution().setZeroes(copy);
if (matrix != copy) {
cout << "MISMATCH\nv1:\n";
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) cout << matrix[i][j] << (j + 1 == c ? '\n' : ' ');
}
cout << "v2:\n";
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) cout << copy[i][j] << (j + 1 == c ? '\n' : ' ');
}
return 0;
}
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j)
cout << matrix[i][j] << (j + 1 == c ? '\n' : ' ');
}
return 0;
}