73. 矩阵置零

难度：🟡 Medium | 标签：矩阵、原地标记 | 状态：⬜ LeetCode 链接

思路

O(1) 空间：用第 0 行 / 第 0 列作为「这行 / 列要清零」的标记位。 但首行首列自己也可能被污染，先单独记录两个 bool。

代码

class Solution {
public:
    void setZeroes(vector<vector<int>>& m) {
        int R = m.size(), C = m[0].size();
        bool row0 = false, col0 = false;
        for (int j = 0; j < C; ++j) if (m[0][j] == 0) row0 = true;
        for (int i = 0; i < R; ++i) if (m[i][0] == 0) col0 = true;
        for (int i = 1; i < R; ++i)
            for (int j = 1; j < C; ++j)
                if (m[i][j] == 0) { m[i][0] = 0; m[0][j] = 0; }
        for (int i = 1; i < R; ++i)
            for (int j = 1; j < C; ++j)
                if (m[i][0] == 0 || m[0][j] == 0) m[i][j] = 0;
        if (row0) for (int j = 0; j < C; ++j) m[0][j] = 0;
        if (col0) for (int i = 0; i < R; ++i) m[i][0] = 0;
    }
};

复杂度

• 时间 O(R · C)，空间 O(1)

易错 / 回顾

• 首行 / 首列必须先单独记录，否则被自己污染
• 顺序：先记 row0/col0，再扫内部、写标记，再清内部，最后清首行首列
• 用 O(R+C) 额外空间的版本更易写，但不是最优