题目链接

题目描述

给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例

示例 1:


输入: matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
输出: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

示例 2:


输入: matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
输出: [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

题解

辅助行和列

通过上图案例,其实我们可以把矩阵看做一个表格,整个矩阵是表格的内容,那我们其实可以通过给为 0 的元素所在的行和列进行标记,可以给表格横向和纵向分别增加一行和一列来存储标记。


辅助行和列示意图
辅助行和列示意图


我们定义行或列存在值为 0 的元素,标记为 true,否则为 false,我们假设矩阵中不包含 0,存储标记行和列的默认值都为 false,只需要遍历矩阵的每一个元素,如果值 0,则将该元素的行标记和列标记都改为 true

根据题目要求,只要元素所在行或列存在 0,即行或列的标记有存在 true 标记,我们就将这一项设置为 0,所以只需再次遍历矩阵根据条件将值设置一遍即可。

const setZeroes = (matrix) => {
  const m = matrix.length;
  const n = matrix[0].length;
  const row = new Array(m).fill(false);
  const col = new Array(n).fill(false);

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

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

复杂度分析:

  • 时间复杂度:$O(m * n)$
  • 空间复杂度:由于创建了行和列的两个辅助数组,空间复杂度为 $O(m + n)$

原地算法

其实题目中明确要求使用 原地 算法,其实就是不使用额外的空间,完成值的置零操作。

在上一个方法基础上延伸思考,如果不能增加额外的行和列来进行标识,那是不是可以用默认的第一行和第一列来标识,假设遍历的某一项值为 0,将所在行和列的第一项进行置零并作为行或列的参考标识,全部标识后再次遍历矩阵,根据标识更改需要置零的元素。


原地算法示意图
原地算法示意图


遍历过程中,以第一列为基准,所以遍历列时应从第一项开始,在置零过程中,防止用于标识的行和列原本就有 0 第一列优先被置零,导致后边元素无法参照标识,所以遍历行时使用反向遍历。

const setZeroes = (matrix) => {
  const m = matrix.length;
  const n = matrix[0].length;
  let flag = false;

  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) {
      flag = true;
    }

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

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

    if (flag) {
      matrix[i][0] = 0;
    }
  }
}

复杂度分析:

  • 时间复杂度:$O(m * n)$
  • 空间复杂度:$O(1)$