73. 矩阵置零

LeetCode 原题链接

题目描述

给定一个 m × n 的整数矩阵。如果某个元素为 0，就将它所在的整行和整列都设为 0。要求直接修改原矩阵，不返回新的矩阵。

输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

题目真正的难点

不能在第一次看到 0 时，立即把对应行和列全部改成 0。

例如：

1 1 1
1 0 1
1 1 1

处理中心的原始 0 时，如果立刻将第二行置零，之后扫描到第二行新产生的 0，就无法判断它是原始 0，还是刚刚被修改出来的 0。继续按照新产生的 0 扩散，最终可能把整个矩阵错误地置零。

所以算法必须分成两个阶段：

  1. 先记录哪些行、哪些列应该置零；
  2. 再根据记录统一修改矩阵。

关键是不能让“写入结果”污染“读取原始信息”的过程。

推荐解法：使用两个集合记录行和列

最容易想到的方案是使用两个 Set：

  • zeroRows：包含原始 0 的行；
  • zeroColumns：包含原始 0 的列。

第一次遍历只记录信息，第二次遍历再修改矩阵。

/**
 * @param {number[][]} matrix
 * @return {void} 直接修改原矩阵
 */
var setZeroes = function (matrix) {
  const rows = matrix.length;
  const columns = matrix[0].length;
  const zeroRows = new Set();
  const zeroColumns = new Set();

  // 第一遍：记录原始 0 所在的行和列
  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
      if (matrix[row][column] === 0) {
        zeroRows.add(row);
        zeroColumns.add(column);
      }
    }
  }

  // 第二遍：所在行或列有原始 0，就置零
  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < columns; column++) {
      if (zeroRows.has(row) || zeroColumns.has(column)) {
        matrix[row][column] = 0;
      }
    }
  }
};

设矩阵大小为 m × n：

  • 时间复杂度：O(mn)；
  • 空间复杂度：O(m + n)。

推荐先掌握这个方法：先记录，再修改，逻辑直接，也不需要特殊处理首行和首列。

直接修改原矩阵不等于额外空间必须是 O(1)。 两个集合的方案直接将结果写回 matrix，满足修改原矩阵的要求；如果进一步要求常数额外空间，再使用下面的优化。两种方案的时间复杂度相同，优化的是额外空间。

进阶：使用矩阵首行和首列作为标记

既然需要分别记录哪些行和列应该置零，可以直接复用矩阵本身：

matrix[row][0]：标记第 row 行是否应该置零
matrix[0][column]：标记第 column 列是否应该置零

扫描内部元素 matrix[row][column] 时，如果发现它等于 0，就写入两个标记：

matrix[row][0] = 0;
matrix[0][column] = 0;

这样便不再需要长度为 m 和 n 的额外数组。

为什么首行和首列必须单独记录

首行和首列既保存原始数据，又会被借用为标记区域，因此它们的含义会发生冲突。

例如：

1 1 0
1 1 1
1 1 1

matrix[0][2] 原本就是 0，所以第一行和第三列都应该置零。

再例如：

1 1 1
0 1 1
1 1 1

matrix[1][0] 原本就是 0，所以第二行和第一列都应该置零。

为了在首行、首列被写入标记之前保存它们的原始状态，需要两个布尔变量：

const firstRowHasZero = matrix[0].some(value => value === 0);

let firstColumnHasZero = false;
for (let row = 0; row < rows; row++) {
  if (matrix[row][0] === 0) {
    firstColumnHasZero = true;
    break;
  }
}

之后内部扫描从 (1, 1) 开始，因为第 0 行和第 0 列已经由这两个变量单独负责。

JavaScript 实现

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function (matrix) {
  const rows = matrix.length;
  const columns = matrix[0].length;

  const firstRowHasZero = matrix[0].some(value => value === 0);
  let firstColumnHasZero = false;

  for (let row = 0; row < rows; row++) {
    if (matrix[row][0] === 0) {
      firstColumnHasZero = true;
      break;
    }
  }

  // 第一遍：用首行和首列记录内部区域中的原始 0
  for (let row = 1; row < rows; row++) {
    for (let column = 1; column < columns; column++) {
      if (matrix[row][column] === 0) {
        matrix[row][0] = 0;
        matrix[0][column] = 0;
      }
    }
  }

  // 第二遍：根据标记修改内部区域
  for (let row = 1; row < rows; row++) {
    for (let column = 1; column < columns; column++) {
      if (matrix[row][0] === 0 || matrix[0][column] === 0) {
        matrix[row][column] = 0;
      }
    }
  }

  // 最后处理被借作标记区域的首行和首列
  if (firstRowHasZero) {
    for (let column = 0; column < columns; column++) {
      matrix[0][column] = 0;
    }
  }

  if (firstColumnHasZero) {
    for (let row = 0; row < rows; row++) {
      matrix[row][0] = 0;
    }
  }
};

执行过程

以下面的矩阵为例：

1 1 1 1
1 0 1 1
1 1 1 0
1 1 1 1

首行和首列原本都没有 0：

firstRowHasZero = false
firstColumnHasZero = false

扫描内部区域：

  • (1, 1) 是 0，将 matrix[1][0] 和 matrix[0][1] 设为 0；
  • (2, 3) 是 0，将 matrix[2][0] 和 matrix[0][3] 设为 0。

标记完成后：

1 0 1 0
0 0 1 1
0 1 1 0
1 1 1 1

此时首行和首列中的部分 0 是标记，不代表它们原本就是 0。

根据标记处理内部区域：

1 0 1 0
0 0 0 0
0 0 0 0
1 0 1 0

由于首行、首列原本没有 0，不需要将它们整体置零。标记位置本身已经是 0，最终结果正好正确。

为什么必须最后处理首行和首列

第二遍处理内部区域时仍然需要读取：

matrix[row][0]
matrix[0][column]

如果提前把首行或者首列整体置零，所有内部元素都会读到 0 标记，导致整个内部区域被错误置零。

正确顺序必须是：

保存首行、首列的原始状态
        ↓
扫描内部区域，写入标记
        ↓
根据标记修改内部区域
        ↓
根据原始状态修改首行、首列

循环不变量与正确性

完成第一次内部遍历后，对于任意 row > 0、column > 0：

matrix[row][0] === 0
⇔ 第 row 行原本存在 0（包括首列）

matrix[0][column] === 0
⇔ 第 column 列原本存在 0（包括首行）

因此第二遍处理内部位置 (row, column) 时，只要它的行标记或列标记为 0，就说明它所在行或列原本包含 0，必须置零；如果两个标记都不是 0，则其所在行列都没有原始 0，应该保留原值。

首行和首列是否应该整体置零，已经在写入标记前分别保存到两个布尔变量中。最后根据布尔变量处理它们，就覆盖了所有位置，并且不会被标记过程污染。

复杂度分析

设矩阵有 m 行、n 列：

  • 时间复杂度：O(mn)。虽然分多次遍历，但每个位置只进行常数次处理。
  • 额外空间复杂度：O(1)。只使用行列数量和两个布尔标记。

输入矩阵本身不计入额外空间。

常见错误

1. 扫描到 0 后立即扩散

新写入的 0 会被后续扫描误认为原始 0，造成连锁污染。

2. 没有保存首行、首列的原始状态

matrix[0][0] 同时属于第一行和第一列，一个格子无法独立表达两组信息。因此至少还需要一个额外变量；使用两个布尔变量通常更容易理解。

3. 第二遍仍然从 (0, 0) 开始

在首行首列标记法中，首行和首列保存的是标记。如果在读取所有标记之前修改它们，就可能让标记失真。第二遍应先只处理内部区域。

4. 忘记题目要求原地修改

函数不需要返回新矩阵：

setZeroes(matrix);

调用结束后，传入的 matrix 已经被修改。

5. 使用宽松相等

矩阵元素是数字，判断时直接使用严格相等：

matrix[row][column] === 0

方案对比

方案时间复杂度额外空间特点
扫描时立即置零可能错误O(1)新产生的 0 会污染判断
两个集合（主解法）O(mn)O(m + n)最直观，推荐先掌握
首行首列作为标记（进阶）O(mn)O(1)节省空间，需要注意处理顺序

一句话总结

先用两个集合记录原始 0 所在的行和列，再统一置零，避免新写入的 0 干扰判断；要求常数额外空间时，再借用首行和首列保存标记。