矩阵置零-73

[sl1673495]

给定一个  m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 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]
]
进阶:

一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-matrix-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

先遍历一次，记录所有刚开始为 0 的点，这点很重要，不能边处理边找 0 点，因为找到一个 0 点后同一行和同一列都会变成 0，会错乱掉。

之后就是遍历所有的 0 点，把排和列全部变成 0，并且把处理过的行和列记录在缓存表中优化性能。

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function (matrix) {
  let maxY = matrix.length
  if (!maxY) return
  let maxX = matrix[0].length

  let handledRows = []
  let handledColumns = []

  let zeros = []
  for (let y = 0; y < maxY; y++) {
    for (let x = 0; x < maxX; x++) {
      let val = matrix[y][x]
      if (val === 0) {
        zeros.push([y, x])
      }
    }
  }

  for (let [y, x] of zeros) {
    if (!handledRows[x]) {
      for (let i = 0; i < maxY; i++) {
        matrix[i][x] = 0
      }
      handledRows[x] = true
    }
    if (!handledColumns[y]) {
      for (let i = 0; i < maxX; i++) {
        matrix[y][i] = 0
      }
      handledColumns[y] = true
    }
  }
}

[Chocolate1999]

坚持打卡！

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
/* 空间复杂度 O(n) */

var setZeroes = function(matrix) {
  let n = matrix.length
  let m = matrix[0].length
  let arr = []
  for(let i=0;i<n;i++){
      for(let j=0;j<m;j++){
          if(matrix[i][j] == 0){
              arr.push([i,j])
          }
      }
  }
  while(arr.length){
      let [x,y] = arr.pop()
      for(let i=0;i<n;i++) matrix[i][y] = 0
      for(let j=0;j<m;j++) matrix[x][j] = 0
  }
  return matrix
};

/* 空间复杂度 O（1） */

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
  for(let i=0;i<matrix.length;i++){
      for(let j=0;j<matrix[0].length;j++){
          if(Object.is(matrix[i][j],0)){
              // 对行进行操作
              for(let k=0;k<matrix.length;k++)
                  if(!Object.is(matrix[k][j],0) && k!==i) matrix[k][j] = -0
              // 对列进行操作
              for(let k=0;k<matrix[0].length;k++)
                  if(!Object.is(matrix[i][k],0) && k!==j) matrix[i][k] = -0
          }
      }
  }
  return matrix
};

[sl1673495]

坚持打卡！

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
/* 空间复杂度 O(n) */

var setZeroes = function(matrix) {
  let n = matrix.length
  let m = matrix[0].length
  let arr = []
  for(let i=0;i<n;i++){
      for(let j=0;j<m;j++){
          if(matrix[i][j] == 0){
              arr.push([i,j])
          }
      }
  }
  while(arr.length){
      let [x,y] = arr.pop()
      for(let i=0;i<n;i++) matrix[i][y] = 0
      for(let j=0;j<m;j++) matrix[x][j] = 0
  }
  return matrix
};

/* 空间复杂度 O（1） */

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
  for(let i=0;i<matrix.length;i++){
      for(let j=0;j<matrix[0].length;j++){
          if(Object.is(matrix[i][j],0)){
              // 对行进行操作
              for(let k=0;k<matrix.length;k++)
                  if(!Object.is(matrix[k][j],0) && k!==i) matrix[k][j] = -0
              // 对列进行操作
              for(let k=0;k<matrix[0].length;k++)
                  if(!Object.is(matrix[i][k],0) && k!==j) matrix[i][k] = -0
          }
      }
  }
  return matrix
};

老哥 自己开个仓库打卡吧 谢谢了。。。

[Chocolate1999]

坚持打卡！

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
/* 空间复杂度 O(n) */

var setZeroes = function(matrix) {
  let n = matrix.length
  let m = matrix[0].length
  let arr = []
  for(let i=0;i<n;i++){
      for(let j=0;j<m;j++){
          if(matrix[i][j] == 0){
              arr.push([i,j])
          }
      }
  }
  while(arr.length){
      let [x,y] = arr.pop()
      for(let i=0;i<n;i++) matrix[i][y] = 0
      for(let j=0;j<m;j++) matrix[x][j] = 0
  }
  return matrix
};

/* 空间复杂度 O（1） */

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
  for(let i=0;i<matrix.length;i++){
      for(let j=0;j<matrix[0].length;j++){
          if(Object.is(matrix[i][j],0)){
              // 对行进行操作
              for(let k=0;k<matrix.length;k++)
                  if(!Object.is(matrix[k][j],0) && k!==i) matrix[k][j] = -0
              // 对列进行操作
              for(let k=0;k<matrix[0].length;k++)
                  if(!Object.is(matrix[i][k],0) && k!==j) matrix[i][k] = -0
          }
      }
  }
  return matrix
};

老哥 自己开个仓库打卡吧 谢谢了。。。

好的，我以为Open了可以提交解题代码的，不好意思哈，打扰了

[sl1673495]

坚持打卡！

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
/* 空间复杂度 O(n) */

var setZeroes = function(matrix) {
  let n = matrix.length
  let m = matrix[0].length
  let arr = []
  for(let i=0;i<n;i++){
      for(let j=0;j<m;j++){
          if(matrix[i][j] == 0){
              arr.push([i,j])
          }
      }
  }
  while(arr.length){
      let [x,y] = arr.pop()
      for(let i=0;i<n;i++) matrix[i][y] = 0
      for(let j=0;j<m;j++) matrix[x][j] = 0
  }
  return matrix
};

/* 空间复杂度 O（1） */

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
  for(let i=0;i<matrix.length;i++){
      for(let j=0;j<matrix[0].length;j++){
          if(Object.is(matrix[i][j],0)){
              // 对行进行操作
              for(let k=0;k<matrix.length;k++)
                  if(!Object.is(matrix[k][j],0) && k!==i) matrix[k][j] = -0
              // 对列进行操作
              for(let k=0;k<matrix[0].length;k++)
                  if(!Object.is(matrix[i][k],0) && k!==j) matrix[i][k] = -0
          }
      }
  }
  return matrix
};

老哥 自己开个仓库打卡吧 谢谢了。。。

好的，我以为Open了可以提交解题代码的，不好意思哈，打扰了

没事 你在自己的仓库里写题解也更有成就感 而且有小绿点可以拿 加油