手帐 Blog

主题

复盘 · LC 73 矩阵置零 ​

题目 ​

题意 ​

给定 m × n 矩阵，若某个元素为 0，则将其所在行和列的所有元素都设为 0。要求原地修改。

  • 注意：不能边扫边改——刚改成的 0 会误伤其它行列。
  • 进阶：额外空间尽量 O(1)。

边界：首行/首列有 0；整行或整列本来就全 0；只有一个 0。

涉及算法 ​

标签一句话
记录行列先记下哪些行/列要清零，再统一写
原地标记用第 0 行 / 第 0 列当「标记位」，额外空间 O(1)

教程对照：数组原地改写手感见 04 · 数组基础题手感；本题是矩阵版「先记标记再写回」。

评价我的解法 ​

独立 AC（211/211）。提交时间约 11ms（约 17%），内存中等——算法档位是「正确的 O(mn) + O(m+n) 空间」，不是错解。

我的代码（摘自 73-矩阵置零/index.js）：

javascript
var setZeroes = function (matrix) {
  const yLen = matrix.length;
  const xLen = matrix[0].length;
  const zeroArr = [];
  const xFillArr = new Set();
  const yFillArr = new Set();
  for (let i = 0; i < yLen; i++) {
    for (let j = 0; j < xLen; j++) {
      if (matrix[i][j] === 0) {
        zeroArr.push({ x: j, y: i });
      }
    }
  }
  for (let i = 0; i < zeroArr.length; i++) {
    const dot = zeroArr[i];
    xFillArr.add(dot.x);
    yFillArr.add(dot.y);
  }

  for (const y of yFillArr) {
    matrix[y].fill(0);
  }

  for (const x of xFillArr) {
    for (let j = 0; j < yLen; j++) {
      matrix[j][x] = 0;
    }
  }
};

对在哪：

  1. 两阶段：先收集零点，再清行列——避开「边改边污染」。
  2. 用 Set 去重行列后批量 fill / 列写零，逻辑清晰，能稳过。
  3. 行清零用 matrix[y].fill(0) 干净。

糙在哪：

  1. zeroArr 多余：扫矩阵时直接 xFillArr.add(j); yFillArr.add(i) 即可，少一次 O(零点个数) 中转和对象分配。
  2. 空间：O(m+n) 的 Set 是常见解；进阶是用第 0 行/第 0 列当标记（再加两个布尔记「第 0 行/列本身是否有零」）。
  3. 命名 x/y 与常见 row/col 反着记也行，但面试口述建议统一「行 i、列 j」。

小结：能独立想出「先记后写」就过关；下一步把空间压到 O(1) 标记法，并删掉中间数组。

最佳题解 ​

O(1) 额外空间：用首行首列做标记。

javascript
/**
 * @param {number[][]} matrix
 * @return {void}
 */
var setZeroes = function (matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  let firstRowZero = false;
  let firstColZero = false;

  for (let j = 0; j < n; j++) {
    if (matrix[0][j] === 0) firstRowZero = true;
  }
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) firstColZero = true;
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
  }

  if (firstRowZero) matrix[0].fill(0);
  if (firstColZero) {
    for (let i = 0; i < m; i++) matrix[i][0] = 0;
  }
};
  • 时间 O(mn)，空间 O(1)。
  • 为何更优：标记存在矩阵自身；最后再处理第 0 行/列，避免互相污染。

你的 Set 版作为「先保证正确」完全合格；进阶口述再补上面这版。

关联题目 ​

题为何相关
289. 生命游戏矩阵原地改，也要「先记状态再写回」
130. 被围绕的区域矩阵标记 + 多源扩散
48. 旋转图像矩阵原地操作手感
36. 有效的数独行列（+宫）用集合记录约束

一句话带走 ​

矩阵置零：先标记要清的行/列，再统一写；进阶把标记塞进第 0 行和第 0 列。