This is the 20th day of my participation in the August More Text Challenge

preface

LeetCode array type problem related solution, can be seen before doing LeetCode array type problem must see, classification solution summary question, can be used to improve each item. If you feel helpful, please remember to pay attention to it. Thank you!

Topic describes

Given an m x n matrix, if one element is 0, set all elements in its row and column to 0. Please use the in place algorithm.

Example 1:

Input: matrix = [[1,1,1],[1,1,1]]

Output: [[1, 1], [0, 0], [1, 1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2]

,0,0,0 output: [[0], [0,4,5,0], [0,3,1,0]]

Link: leetcode-cn.com/problems/se…

Answer key

The whole point of this problem is to mark the rows and columns where 0 appears. Here are the steps:

  1. Row [I] specifies whether the ith row has a 0 number. Initialize each element to 0.

  2. If matrix[I][j] is 0, set row[I] to 1 and col[j] to 1.

  3. Modify the original array matrix. Traverse the elements in matrix. If the corresponding array of row and column markers is 0, there is no need to modify the element.

The specific code is shown below, the time complexity is O(mn), the space complexity is O(m+n), there is a way to reduce the space complexity, using two marker variables to replace the row and COL marker array, readers can achieve their own.

/ * * *@param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function(matrix) {
    const m = matrix.length
    const n = matrix[0].length
    let row = new Array(m).fill(0)
    let col = new Array(n).fill(0)
    // Mark the array
    for (let i = 0; i < m; ++i) {
      for (let j = 0; j < n; ++j) {
        if(! matrix[i][j]) { row[i] =1
          col[j] = 1}}}for (let i = 0; i < m; ++i) {
      for (let j = 0; j < n; ++j) {
        if (row[i] || col[j]) {
          matrix[i][j] = 0}}}};Copy the code