73. Set Matrix Zeroes

Leetcode

https://leetcode.com/problems/set-matrix-zeroes/

題目

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's, and return the matrix.

You must do it in place.

Follow up:

• A straightforward solution using O(mn) space is probably a bad idea.

• A simple improvement uses O(m + n) space, but still not the best solution.

• Could you devise a constant space solution?

解答

• 方法一

先遍歷所有矩陣元素，找出為零的位置，之後再把同一欄、同一列都設成 0

var setZeroes = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    
    const rows = [];
    const cols = [];
    for(let i=0; i<m; i++) {
      for(let j=0; j<n; j++) {
          if(matrix[i][j] === 0) {
              rows.push(i);
              cols.push(j);
          }
      }
    }
    
    for(let i=0; i<rows.length; i++) {
      const row = rows[i];
      for(let j=0; j<n; j++) {
          matrix[row][j] = 0;
      }
    }
    for(let j=0; j<cols.length; j++) {
      const col = cols[j];
      for(let i=0; i<m; i++) {
          matrix[i][col] = 0;
      }
    }
};

Runtime: 100 ms, faster than 62.26% of JavaScript online submissions for Set Matrix Zeroes.

Memory Usage: 41 MB, less than 76.94% of JavaScript online submissions for Set Matrix Zeroes.

測資

let matrix = [[1,1,1],[1,0,1],[1,1,1]]
matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]];

setZeroes(matrix);
console.log(matrix);