Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Recently in the LeetCode brush problem, there is a satisfactory solution to the problem, I would like to share with you. So here’s the title, 73. Matrix zero for those of you who are interested.

I didn’t think about n2 because they gave me a hint about constant space, so the initial idea is this

  1. Go through the array and find the position of 0matrix[i][j]
  2. Convert 2-d coordinates to 1-D indexes
  3. Store in an indexed arrayzeros
  4. Reading group, parsing index
  5. Modify the original array

Let’s talk about step 2. Convert 2d coordinates to 1d index. This step should have a name, but I forget what its name is. Index = I * matrix[0]. Length + j, which is the ordinal = x * column number + y. I = index/matrix[0].length; j = index % matrix[0].length

Start the first wave of masturbation code:

 / * * *@param {number[][]} matrix
  * @return {void} Do not return anything, modify matrix in-place instead.
  */
 var setZeroes = function(matrix) {
     let zeros = []
     for (let i = 0; i < matrix.length; i++) {
         for (let j = 0; j < matrix[0].length; j++) {
             if (matrix[i][j] === 0) {
                 zeros.push(i * matrix[0].length + j)
             }
         }
     }
     zeros.forEach((val) = > {
         matrix[val / matrix[0].length] = new Array(matrix[0].length).fill(0)
         for (let i = 0; i < matrix.length; i++) {
             matrix[i][val % matrix[0].length] = 0}})};Copy the code

There is a slight error in this wave of code at line 15, because JavaScript defaults to floating-point division, so the result might be a decimal and then found in matrix[] is undefined.

Modify:

 zeros.forEach((val) = > {
     matrix[Number.parseInt(val / matrix[0].length)] = new Array(matrix[0].length).fill(0)
     for (let i = 0; i < matrix.length; i++) {
         matrix[i][val % matrix[0].length] = 0}})Copy the code

This is not a very smart solution. The argument to number.parseint () is actually a String, so this is not a good solution.

Change it again:

 zeros.forEach((val) = > {
     matrix[Math.floor(val / matrix[0].length)].fill(0)
     for (let i = 0; i < matrix.length; i++) {
         matrix[i][val % matrix[0].length] = 0}})Copy the code

Using math.floor () is not only faster but also easier to read because it’s all number operations.

The overall code looks like this:

 / * * *@param {number[][]} matrix
  * @return {void} Do not return anything, modify matrix in-place instead.
  */
 var setZeroes = function(matrix) {
     let zeros = []
     for (let i = 0; i < matrix.length; i++) {
         for (let j = 0; j < matrix[0].length; j++) {
             if (matrix[i][j] === 0) {
                 zeros.push(i * matrix[0].length + j)
             }
         }
     }
     zeros.forEach((val) = > {
         matrix[Math.floor(val / matrix[0].length)].fill(0)
         for (let i = 0; i < matrix.length; i++) {
             matrix[i][val % matrix[0].length] = 0}})};Copy the code

Look at the result is not bad, hahaha ~

\