矩阵置零-73 #111

sl1673495 · 2020-06-29T14:37:14Z

给定一个 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 · 2020-09-12T15:54:49Z

坚持打卡！

/**
 * @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 · 2020-09-12T15:56:20Z

坚持打卡！

/**
 * @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 · 2020-09-12T15:57:37Z

坚持打卡！

/**
 * @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 · 2020-09-12T15:59:51Z

坚持打卡！

/**
 * @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 added the 递归与回溯 label Jun 29, 2020

Oct	NOV	Dec
	29
2019	2020	2021

sl1673495 / leetcode-javascript

矩阵置零-73 #111

矩阵置零-73 #111

sl1673495 commented Jun 29, 2020

Chocolate1999 commented Sep 12, 2020

sl1673495 commented Sep 12, 2020

Chocolate1999 commented Sep 12, 2020

sl1673495 commented Sep 12, 2020

sl1673495 / leetcode-javascript

Join GitHub today

GitHub is where the world builds software

矩阵置零-73 #111

矩阵置零-73 #111

Comments

sl1673495 commented Jun 29, 2020

思路

Chocolate1999 commented Sep 12, 2020

sl1673495 commented Sep 12, 2020

Chocolate1999 commented Sep 12, 2020

sl1673495 commented Sep 12, 2020

Essential cookies

Always active

Analytics cookies