LeetCode 73. Set Matrix Zeroes

Quesiton

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

click to show follow up.

Follow up: Did you use extra space? A straight forward 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?

Explanation

主题思想就是利用第一行和第一列来记录哪些行和列需要标记为0。同时，用两个boolean变量标记第一行和第一列本身是否需要标记为0。

Code

public class Solution {
public void setZeroes(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
    int m = matrix.length, n = matrix[0].length;
    boolean row = false, col = false;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++){
            if (matrix[i][j] == 0) {
                matrix[0][j] = 0;
                matrix[i][0] = 0;
                if (i == 0) row = true;
                if (j == 0) col = true;
            }
        }
    for (int i = 1; i < m; i++){
        if (matrix[i][0] == 0){
            for (int j = 1; j < n;j++)
                matrix[i][j] = 0;
        }
    }
    for (int j = 1; j < n; j++){
        if (matrix[0][j] == 0){
            for (int i = 1; i < m; i++)
                matrix[i][j] = 0;
        }
    }
    if (row){
        for (int j = 0; j < n; j++)
            matrix[0][j] = 0;
    }
    if (col){
        for(int i = 0; i < m; i++)
            matrix[i][0] = 0;
    }
}
}