yicong@algo: ~/code/06-matrix/0073-set-matrix-zeroes.cpp

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;
}