73. Set Matrix Zeroes

O(m+n) 的思路：扫一遍matrix，hash set记录需要置0的行列。第二遍置0。O(m+n) 来自两个hash set

O(1)的思路：用两个变量表示，第一行和第一列需不需要置0。用第一行和第一列充当前面的hash set

空间复杂度O(m+n)

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */

// O(m+n)
var setZeroes = function (matrix) {
  const row_to_zeros = new Set()
  const col_to_zeros = new Set()
  for (let row = 0; row < matrix.length; row++) {
    for (let col = 0; col < matrix[row].length; col++) {
      if (matrix[row][col] === 0) {
        row_to_zeros.add(row)
        col_to_zeros.add(col)
      }
    }
  }
  console.log(row_to_zeros, col_to_zeros)
  for (let row = 0; row < matrix.length; row++) {
    if (row_to_zeros.has(row)) {
      for (let col = 0; col < matrix[row].length; col++) {
        matrix[row][col] = 0
      }
    }
  }
  for (let col = 0; col < matrix[0].length; col++) {
    if (col_to_zeros.has(col)) {
      for (let row = 0; row < matrix.length; row++) {
        matrix[row][col] = 0
      }
    }
  }
}

空间复杂度O(1)

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function (matrix) {
  let first_row_to_zeros = false
  let first_col_to_zeros = false
  for (let row = 0; row < matrix.length; row++) {
    for (let col = 0; col < matrix[0].length; col++) {
      if (matrix[row][col] === 0) {
        if (row === 0) {
          first_row_to_zeros = true
        }
        if (col === 0) {
          first_col_to_zeros = true
        }
        matrix[0][col] = 0
        matrix[row][0] = 0
      }
    }
  }

  for (let row = 1; row < matrix.length; row++) {
    // 跳过第一行，留到最后修改
    for (let col = 1; col < matrix[0].length; col++) {
      // 跳过第一列，留到最后修改
      if (matrix[0][col] === 0 || matrix[row][0] === 0) {
        matrix[row][col] = 0
      }
    }
  }
  if (first_col_to_zeros) {
    for (let row = 0; row < matrix.length; row++) {
      matrix[row][0] = 0
    }
  }
  if (first_row_to_zeros) {
    for (let col = 0; col < matrix[0].length; col++) {
      matrix[0][col] = 0
    }
  }
}