73 矩阵置零

题目

给定一个 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) 的额外空间，但这仍然不是最好的解决方案。 你能想出一个常数空间的解决方案吗？

题解

1. 如果要修改原数组，需要先把为 0 的元素找出来，然后在修改。那么第一次遍历寻找为 0 的元素的 index；第二次遍历去修改对应的位置。

TIP

执行用时：100 ms, 在所有 JavaScript 提交中击败了 88.14% 的用户
内存消耗：40.5 MB, 在所有 JavaScript 提交中击败了 27.92% 的用户

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    let zeroInfo = [] // 用来储存为 0 元素的 index，index 为一个数组，分别为一维数组的 index 和二维数组的 index。
    matrix.forEach((item,idx)=>{
        let startIdx = item.indexOf(0, 0) // 从起点开始寻找 0，并记录 index

            // 如果找到了
        while (startIdx > -1) {
            zeroInfo.push([idx, startIdx])  // 把 index 数组存起来
            startIdx = item.indexOf(0, startIdx + 1)  // 从 index + 1 也就是下一个位置开始查找
        }

    })

    // 如果找到 0 了，那么就进行遍历
    for (let i = 0, l = zeroInfo.length; i < l; i++) {
        let[first,second] = zeroInfo[i] // 解构分别获取第一个位置和第二个位置

        matrix.forEach((item,idx)=>{
            item[second] = 0 // 把竖排的元素修改为 0
            if (idx === first) {
                item.fill(0)  // 把横排的元素修改为 0，也就是整个数组
            }
        })
    }
    return matrix
};

• 时间复杂度： `O(n^2)`，使用了一个 forEach 嵌套了 while循环
• 空间复杂度： `O(mn)`，zeroInfo 的空间大小取决于为 0 元素的数量
• 最好情况： 没有元素为 0，则不需要进入 while循环，或者为 0元素较少。
• 最坏情况： 为 0 元素较多，则 while循环需要经过多次遍历操作，同时第二个赋值 0 的操作也需要进行多次