73. Set Matrix Zeroes

二刷
和一刷做法基本一样
第一行表示每一个column是否是0，第一列表示每一行是否是0
matrix[0][0] 既可以表示第一行也可以表示第一列所以产生了歧义
r0代表的是第一行是否是0
matrix[0][0]表示第一列是否是0

Time O(mn) Space O(1)
100.00 %
class Solution {
    public void setZeroes(int[][] matrix) {
        // matrix[0][j] -> for the columns
        // matrix[i][0] -> for the rows
        int rows = matrix.length, cols = matrix[0].length;
        int r0 = -1; // r0 for the 1st row
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) {
                        r0 = 0;
                    } else {
                        matrix[i][0] = 0;
                    }
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (matrix[0][0] == 0) {
            for (int i = 0; i < rows; i++) {
                matrix[i][0] = 0;
            }
        }
        if (r0 == 0) {
            for (int j = 0; j < cols; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}

一刷
两个bug
1.虽然boolean 的default值是false,但是如果在后面要用这个boolean值而没有初始化的话，会报"XXX might not be initialized" 所以必须初始化

2.第二遍置零的时候两层for loop 都要从1开始，一旦matrix[0][0]是0的话后面整个matrix都是全0

一开始想法是遇到0之后把它的行和列都设为x，最后再扫一遍
但是这样的时间复杂度是O(mn(m + n))


现在这个方法用第一行和第一列代表了整个matrix的状态，用两个boolean 代表了第一行和第一列的状态，时间复杂度是O(mn)
22.97 %

public class Solution {
 
    //use the 1st row/column to represent which column/row should be set to zeroes
    //use 2 booleans (firstRow, firstCol) to represent if the first row/column shoule be set to zeroes
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean firstRow = false, firstCol = false;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (matrix[row][col] == 0) {
                    if (row == 0) firstRow = true;
                    if (col == 0) firstCol = true;
                    matrix[row][0] = 0;
                    matrix[0][col] = 0;        
                }
            }
        }
     
        for (int row = 1; row < rows; row++) {
            for (int col = 1; col < cols; col++) {
                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
                    matrix[row][col] = 0;      
                }
            }
        }
        if (firstRow) {
            for (int j = 0; j < cols; j++) {
                matrix[0][j] = 0;
            }
        }
        if (firstCol) {
            for (int i = 0; i < rows; i++) {
                matrix[i][0] = 0;
            }
        }
     
    }
}