73. Set Matrix Zeroes

leetcode
92

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

  • A straight forward solution using O(m**n) 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?

Example 1:

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

Example 2:

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

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2<sup>31</sup><span> </span><= matrix[i][j] <= 2<sup>31</sup><span> </span>- 1
思路

题目意思是说一个mxn的矩阵，如果某位上是0，那么该点所在行和所在列都设置成0，要求in place，说明只能在原来矩阵上操作。可以考虑使用每一行和每一列来记录该行该列是否设置位0，这时候就需要考虑第一列或者第一行是否需要被刷成0，使用matrix[0][0]来判断就行。

代码

golang:

func setZeroes(matrix [][]int)  {
    var row0IsZero bool
    
    m := len(matrix)
    n := len(matrix[0])
    
    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 {
            row0IsZero = true
        }
        // 从第二列开始扫，第一列用来记录是否需要刷成0
        for j := 1; j < n; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }
    
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 1; j-- {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
        
        // 判断每行首位需不需要置为0
        if row0IsZero {
            matrix[i][0] = 0
        }
    }
}