https://leetcode-cn.com/problems/set-matrix-zeroes/
点击查看【bilibili】

题目

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
**
原地算法：不能开辟新的数组，只在原数据进行修改

示例

  1. 输入: 
  2. [
  3.   [1,1,1],
  4.   [1,0,1],
  5.   [1,1,1]
  6. ]
  7. 输出: 
  8. [
  9.   [1,0,1],
  10.   [0,0,0],
  11.   [1,0,1]
  12. ]

image.png

  1. 输入: 
  2. [
  3.   [0,1,2,0],
  4.   [3,4,5,2],
  5.   [1,3,1,5]
  6. ]
  7. 输出: 
  8. [
  9.   [0,0,0,0],
  10.   [0,4,5,0],
  11.   [0,3,1,0]
  12. ]

image.png

解答

  1. 检查并标记第一行和第一列是否有0

    (firstColHasZero 和 firstRowHaszero)

  2. 使用第一行和第一列,来标记其余行列是否含有0

  3. 接下来,利用第一行和第一列的标0情况,将matrix中的数字标0
  4. 最后,处理第一行和第一列

如果 firstColHasZero等于true将第一列全设为0
如果 firstRowHaszero等于true将第一行全设为0

答案

  1. /**
  2.  * @param {number[][]} matrix
  3.  * @return {void} Do not return anything, modify matrix in-place instead.
  4.  */
  5. var setZeroes = function(matrix) {
  6.     let firstColHasZero = false; // 第一列
  7.     let firstRowHaszero = false; // 第一行
  8.     // 检查第一列是否有0
  9.     for(let i=0;i<matrix.length;i++) {
  10.         if(matrix[i][0] === 0) {
  11.             firstColHasZero = true
  12.         }
  13.     }
  14.     // 检查第一行是否有0
  15.     for(let i=0;i<matrix[0].length;i++) {
  16.         if(matrix[0][i] === 0) {
  17.             firstRowHaszero = true
  18.         }
  19.     }
  20.     // 使用第一行和第一列，来标记其余行列是否含有0
  21.     for(let row=1;row<matrix.length;row++) {
  22.       for(let col=1;col<matrix[0].length;col++) {
  23.         if(matrix[row][col] === 0) {
  24.           matrix[row][0] = 0
  25.           matrix[0][col] = 0
  26.         }
  27.       }
  28.     }
  29.     // 接下来，利用第一行和第一列的标0情况。将matrix中的数字标0
  30.     for(let row=1;row<matrix.length;row++) {
  31.       for(let col=1;col<matrix[0].length;col++) {
  32.         if(matrix[row][0] === 0 || matrix[0][col] === 0) {
  33.           matrix[row][col] = 0
  34.         }
  35.       }
  36.     }
  37.     // 最后，处理第一行和第一列
  38.     // 如果firstColHasZero等于true，将第一列全设为0
  39.     if(firstColHasZero) {
  40.       for(let i=0;i<matrix.length;i++) {
  41.         matrix[i][0] = 0
  42.       }
  43.     }
  44.     //如果firstRowHaszero等于true，将第一行全设为0
  45.     if(firstRowHaszero) {
  46.       for(let i=0;i<matrix[0].length;i++) {
  47.         matrix[0][i] = 0
  48.       }
  49.     }
  50.     return matrix
  51. };

进阶

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