中等

问题描述

编写一种算法，若M × N矩阵中某个元素为 0，则将其所在的行与列清零。

示例 1：

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

示例 2：

输入：
[
 [0,1,2,0],
 [3,4,5,2],
 [1,3,1,5]
]
输出：
[
 [0,0,0,0],
 [0,4,5,0],
 [0,3,1,0]
]

数组标记

遍历一次矩阵，记录数组记录需要置零的行和列下标，记录完毕后再次遍历矩阵，将对应的行和列置零。

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function (matrix) {
  const n = matrix.length
  const m = matrix[0].length
  const rows = new Array(n).fill(false)
  const cols = new Array(n).fill(false)
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (matrix[i][j] === 0) {
        rows[i] = true
        cols[j] = true
      }
    }
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (rows[i] || cols[j]) {
        matrix[i][j] = 0
      }
    }
  }
}

• 时间复杂度：$O(n \times m)$
• 空间复杂度：$O(n + m)$