跳到主要内容

LeetCode 73. 矩阵置零

本节目标

借用首行首列保存清零标记，在常数额外空间内完成矩阵更新。

这道题是矩阵解题框架的第一道母题。重点不是找到零，而是在不破坏原始判断依据的前提下，把“哪些行列需要清零”记录下来。

查看原题

题意与约束​

给定一个 m × n 整数矩阵。若某个位置为 0，就把它所在的整行和整列都改成 0。要求直接修改输入矩阵。

第一反应：遇到零就立刻清空​

边扫描边清空会制造新的零。后续扫描无法区分“原本就是零”和“刚被改成零”，清零范围会不断扩散。

用两个额外数组分别记录需要清零的行和列可以正确解决，空间复杂度为 O(m + n)。进一步观察，矩阵的首行和首列本身就能承担这两个标记数组的职责。

首行首列作为标记​

先单独记录首行、首列原本是否含零，然后只扫描内部区域：

  • 若 matrix[row][col] == 0，令 matrix[row][0] = 0；
  • 同时令 matrix[0][col] = 0。

扫描结束后，首列保存行标记，首行保存列标记。根据它们清空内部区域，最后再根据两个布尔值处理首行和首列。

顺序不能交换：首行首列既是数据又是标记，如果过早清空，就会丢失标记含义。

原地修改​

函数没有返回值，而是直接修改原矩阵。首行首列在第一阶段暂存标记；内部区域清零完成后，最后恢复它们应有的结果。调用者应在函数执行后读取同一个矩阵对象。

代码实现​

两种语言都使用相同的三阶段流程：记录首边界、标记并清空内部、最后处理首边界。

C++17
#include <vector>
using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) {
            return;
        }

        int rows = static_cast<int>(matrix.size());
        int cols = static_cast<int>(matrix[0].size());
        bool firstRowZero = false;
        bool firstColZero = false;

        for (int col = 0; col < cols; col++) {
            if (matrix[0][col] == 0) {
                firstRowZero = true;
            }
        }
        for (int row = 0; row < rows; row++) {
            if (matrix[row][0] == 0) {
                firstColZero = true;
            }
        }

        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                if (matrix[row][col] == 0) {
                    matrix[row][0] = 0;
                    matrix[0][col] = 0;
                }
            }
        }

        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
                    matrix[row][col] = 0;
                }
            }
        }

        if (firstRowZero) {
            for (int col = 0; col < cols; col++) {
                matrix[0][col] = 0;
            }
        }
        if (firstColZero) {
            for (int row = 0; row < rows; row++) {
                matrix[row][0] = 0;
            }
        }
    }
};

复杂度分析​

  • 时间复杂度：O(mn)，每个位置只被常数次访问。
  • 空间复杂度：O(1)，只使用两个布尔变量，标记存放在原矩阵中。

易错点​

  • 扫描到零就立即清行清列，导致零扩散。
  • 没有单独保存首行和首列是否原本含零。
  • 先处理首行首列，再根据它们清空内部，破坏标记。
  • 忘记题目要求原地修改，返回一份新矩阵。

模式迁移​

当题目要求记录“整行、整列稍后处理”且额外空间受限时，可以寻找一行一列作为标记区。迁移前要确认两点：标记区原本的信息如何保存，以及最终应在什么时机恢复或覆盖它。