73. Set Matrix Zeroes

Question:

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

Example 1:

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

Example 2:

Input:
[
  [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]
]

Follow up:

• 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?

Thinking:

• Method1:
  • 通过一个二维数组记录0的位置。
• Method2:
  • 通过两个一维数组记录0的位置（可以记录出哪一行哪一列需要清零）。
• Method3：
  • 通过两个boolean变量记录第一行或第一列需要清零，再将第一行和第一列作为Method2中的两个一维数组。

class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix == null || matrix.length == 0) return;
        int height = matrix.length;
        int width = matrix[0].length;
        boolean firstRow = false, firstCol = false;
        for(int i = 0; i < height; i++){
            if(matrix[i][0] == 0){
                firstCol = true;
                break;
            }
        }
        for(int i = 0; i < width; i++){
            if(matrix[0][i] == 0){
                firstRow = true;
                break;
            }
        }
        for(int i = 1; i< width; i++){
            for(int j = 1; j< height; j++){
                if(matrix[j][i] == 0){
                    matrix[j][0] = 0;
                    matrix[0][i] = 0;
                }
            }
        }
        for(int i = 1; i < width; i++){
            if(matrix[0][i] == 0)   clearCol(matrix, i);
        }
        for(int i = 1; i < height; i++){
        	if(matrix[i][0] == 0) clearRow(matrix, i);
        }
        if(firstRow) clearRow(matrix, 0);
        if(firstCol) clearCol(matrix, 0);
    }
    private static void clearRow(int[][] matrix, int row){
        for(int i = 0; i < matrix[0].length; i++)
            matrix[row][i] = 0;
    }
    private static void clearCol(int[][] matrix, int col){
        for(int i = 0; i < matrix.length; i++)
            matrix[i][col] = 0;
    }
}

二刷

还是能回忆起一刷时候的方法。但是要注意一点，应该将清除行，清除列封装起来，这样可以减少很多代码。

class Solution {
    public void setZeroes(int[][] matrix) {
        int height = matrix.length, width = matrix[0].length;
        boolean firstRow = false, firstCol = false;
        for(int i = 0; i < height; i++)
            if(matrix[i][0] == 0) firstCol = true;
        for(int i = 0; i < width; i++)
            if(matrix[0][i] == 0) firstRow = true;
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1; i < height; i++)
            if(matrix[i][0] == 0) clearRow(matrix, i);
        for(int i = 1; i < width; i++)
            if(matrix[0][i] == 0) clearCol(matrix, i);
        if(firstRow) clearRow(matrix, 0);
        if(firstCol) clearCol(matrix, 0);
    }
    private void clearRow(int[][] matrix, int row){
        int width = matrix[0].length;
        for(int i = 1; i < width; i++){
            matrix[row][i] = 0;
        }
    }
    private void clearCol(int[][] matrix, int col){
        int height = matrix.length;
        for(int i = 0; i < height; i++){
            matrix[i][col] = 0;
        }
    }
}

Amazon session

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