力扣挑战赛第7天-No.73矩阵置零

题目描述

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

示例：

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

输入：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]
]

注意：

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2 ** 31 <= matrix[i][j] <= 2 ** 31 - 1

解法一

三重遍历，先标记，再替换，时间复杂度较高，不推荐

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
let setZeroes = function (matrix) {
  let m = matrix.length;
  let n = matrix[0].length;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === 0) {
        for (let x = 0; x < n; x++) {
          if (matrix[i][x] !== 0) {
            matrix[i][x] = 'will';
          }
        }
        for (let x = 0; x < m; x++) {
          if (matrix[x][j] !== 0) {
            matrix[x][j] = 'will';
          }
        }
      }
    }
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === 'will') {
        matrix[i][j] = 0;
      }
    }
  }
};

解法二

使用第一行和第一列来标记某个元素是否是 0，最后进行替换，不过需要两个标记变量来记录第一行和第一列是否原本就存在 0

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
let setZeroes = function (matrix) {
  let m = matrix.length;
  let n = matrix[0].length;
  let firstRow = false;
  let firstColumn = false;
  for (let j = 0; j < n; j++) {
    if (matrix[0][j] === 0) {
      firstRow = true;
    }
  }
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) {
      firstColumn = true;
    }
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][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 (firstRow) {
    for (let j = 0; j < n; j++) {
      matrix[0][j] = 0;
    }
  }
  if (firstColumn) {
    for (let i = 0; i < m; i++) {
      matrix[i][0] = 0;
    }
  }
}

解法三

类似于解法二，不过只使用一个标记变量，记录第一列是否原本存在 0，而第一列的第一个元素用来记录第一行是否原本存在 0，注意，为防止每一列的第一个元素被提前更新，需要从最后一行开始，倒序地处理矩阵元素

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

Donate