73. 矩阵置零

2021 年 03 月 21 日 链接：https://leetcode-cn.com/problems/set-matrix-zeroes/

题目

描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地（空间复杂度为 0(1)）算法。

示例

示例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) 的额外空间，但这仍然不是最好的解决方案。

• 你能想出一个常数空间的解决方案吗？

  解答

  思路

  此处直接参照官网第三种解题思路

• 创建标记，用于记录第一列是否有零

• 使用双重 for 循环遍历数组，外循环从第一行开始内循环，先单独处理第一列，然后从第二列开始循环
  • 如果第一列的元素是零，将标记更新 true
  • 如果其他列的元素是零，将当前行的首元素和当前列的首元素标记为 0，这目的是为了标记当前行和列需要置为 0

• 再次使用双重 for 循环重新遍历数组，外循环从最后一行开始，内循环从第二列开始循环，然后单独处理第一列

  此时若从第一行开始外循环的话，会出现标记信息丢失。因为第一行的信息还有标记作用。想象下当原数组中第一行就有 0，即此时第一行第一列为 0，那么执行此循环就会将第一行全部更新为零，导致标记信息丢失

  • 先判断其他列，检查列首和行首，如果其他列的元素所在行的首元素或者所在列的首元素为 0，那么当前元素置为 0

  • 最后处理第一列，检查标记，如果标记是 true 那么第一列的当前元素置为 0

    代码

    /**
    * @param {number[][]} matrix
    * @return {void} Do not return anything, modify matrix in-place instead.
    */
    var setZeroes = function(matrix) {
    // 标记首列是否有 0
    let flag = false
    // 行的长度
    let xLength = matrix[0].length
    // 列的长度
    let yLength = matrix.length
    // 遍历数组，记录数组中出现 0 的位置
    for(let i = 0; i < yLength; i ++){
      // 遍历第 1 列
      if(matrix[i][0] === 0){
          flag = true
      }
      // 遍历第 2 到 xLength 列
      // 如果有 0 将对应列的第一个元素标为 0，对应行的第一个元素标为 0
      for(let j = 1; j < xLength; j ++){
          if(matrix[i][j] === 0){
              matrix[i][0] = 0
              matrix[0][j] = 0 
          }
      }
    }
    // 遍历数组，将出现 0 的行与列上的元素替换成 0
    for(let i = yLength - 1; i >= 0; i --){
      // 如果当前元素的行首和列首有 0 的话，将当前元素置为 0
      for(let j = 1; j < xLength; j ++){
          if(matrix[i][0] === 0 || matrix[0][j] === 0){
              matrix[i][j] = 0
          }
      }
      // 如果首列有 0，则当前行的第一个元素要置为 0
      if(flag === true){
          matrix[i][0] = 0
      }
    }
    return matrix
    };