73、矩阵置零

;(function () {
  /**
     * 73. 矩阵置零
     * 
     * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
     * 
     * 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
     * 输出：[[1,0,1],[0,0,0],[1,0,1]]
     * 
     * 输入：matrix = [[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) 的额外空间，但这仍然不是最好的解决方案。
        你能想出一个仅使用常量空间的解决方案吗？
     * 
     */

  /**
     Do not return anything, modify matrix in-place instead.
    */
  function setZeroes(matrix: number[][]): void {
    // 方法一
    // // 思路：遍历数组中的 0，标记【行中有0】和【列中有0】的项，最后再遍历将这些项全部设置为 0
    // // 备注： 标记的方式可以是 【下标插入数组】或【下标插入对象（为对象属性，值为true）】
    // let rows: number[] = [];
    // let columns: number[] = [];
    // // 标记【行中有0】和【列中有0】的项
    // matrix.map((arr, k) => {
    //     arr.map((item, index) => {
    //         if (item === 0) {
    //             rows.push(k);
    //             columns.push(index);
    //         }
    //     })
    // })
    // let rowsAfterSet = [...Array.from(new Set(rows))];
    // let columnsAfterSet = [...Array.from(new Set(columns))];
    // // 遍历将这些项全部设置为 0
    // matrix.map((arr, k) => {
    //     arr.map((item, index) => {
    //         // 行 / 列 被标记(includes)的项，设置为 0
    //         rowsAfterSet.includes(k) || columnsAfterSet.includes(index) ? matrix[k][index] = 0 : null;
    //     })
    // })

    // 方法二：使用两个标记变量
    // const r = matrix.length, c = matrix[0].length;
    // let flagR0 = false, flagC0 = false;
    // // 1. 判断 第一行 / 第一列 中是否有 0
    // for (let i = 0; i < r; i++) {
    //     matrix[i][0] === 0 ? flagC0 = true : null;
    // }
    // for (let j = 0; j < c; j++) {
    //     matrix[0][j] === 0 ? flagR0 = true : null;
    // }
    // // 2. 其他行/列 处理 第一行/列
    // for (let i = 1; i < r; i++) {
    //     for (let j = 1; j < c; j++) {
    //         if (matrix[i][j] === 0) {
    //             matrix[i][0] = matrix[0][j] = 0;
    //         }
    //     }
    // }
    // // 3. 第一行/列 反过来处理 其他行/列
    // for (let i = 1; i < r; i++) {
    //     for (let j = 1; j < c; j++) {
    //         if (matrix[i][0] === 0 || matrix[0][j] === 0) {
    //             matrix[i][j] = 0;
    //         }
    //     }
    // }
    // // 4. 使用两个标记变量更新第一行与第一列
    // if (flagC0) {
    //     for (let i = 0; i < r; i++) {
    //         matrix[i][0] = 0;
    //     }
    // }
    // if (flagR0) {
    //     for (let j = 0; j < c; j++) {
    //         matrix[0][j] = 0;
    //     }
    // }

    // 方法三：使用一个标记变量
    const m = matrix.length,
      n = matrix[0].length
    let flagCol0 = false
    for (let i = 0; i < m; i++) {
      if (matrix[i][0] === 0) {
        flagCol0 = true
      }
      for (let j = 1; j < n; j++) {
        if (matrix[i][j] === 0) {
          matrix[i][0] = matrix[0][j] = 0
        }
      }
    }
    for (let i = m - 1; i >= 0; i--) {
      for (let j = 1; j < n; j++) {
        if (matrix[i][0] === 0 || matrix[0][j] === 0) {
          matrix[i][j] = 0
        }
      }
      if (flagCol0) {
        matrix[i][0] = 0
      }
    }
  }

  let matrix = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
  ]
  setZeroes(matrix)
  console.log(matrix)
})()
73、矩阵置零 ​

73、矩阵置零
