Set Matrix Zeros

Leave a comment

November 22, 2016 by oneOokay

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


题目要do it in place,所以难度在于区别这些0是原本的0还是transform的0.

我AC的想法是两个Set,一个存存在0的col数,一个存存在0的row数;扫两遍第一遍填好两个set,第二遍根据两个Set来set 0.

所以这里extra space用的是O(N);可以优化到O(1)。

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return;
        }
        Set col = new HashSet<>();
        Set row = new HashSet<>();
        
        for (int i = 0; i < matrix.length; i ++){
            for (int j = 0; j < matrix[0].length; j ++){
                if (matrix[i][j] == 0){
                    if (!row.contains(i)){
                        row.add(i);
                    }
                    if (!col.contains(j)){
                        col.add(j);
                    }
                }
            }
        }
        for (int i = 0; i < matrix.length; i ++){
            for (int j = 0; j < matrix[0].length; j ++){
                if (row.contains(i) || col.contains(j)){
                    matrix[i][j] = 0;
                }
            }
        }
    }    
}

优化到O(1)的方法是:

  1. 用第一行和第一列来代替我的两个Sets当marker;两个boolean来标示第一行和第一列是否本身含有0。
  2. 一次扫描整个表,遇到0的话就标记在第一行和第一列上;同时如果遇到第一行和第一列有0的话,把相应的boolean设置成true。
  3. 第二行第二列开始扫描,根据第一行和第一列的标记将整行整列标0.
  4. 最后再根据两个boolean来决定是否把第一行和第一列归0
public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return;
        }
        boolean firstRow = false;
        boolean firstCol = false;
        for (int i = 0; i < matrix.length; i ++){
            for (int j = 0; j < matrix[0].length; j ++){
                if (matrix[i][j] == 0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                    if (i == 0) firstRow = true;
                    if (j == 0) firstCol = true;
                }
            }
        }
        
        for (int i = 1; i < matrix.length; i ++){
            if (matrix[i][0] == 0){
                setRowZeros(i, matrix);
            }
        }
        
        for (int i = 1; i < matrix[0].length; i ++){
            if (matrix[0][i] == 0){
                setColZeros(i, matrix);
            }
        }
        
        if (firstRow){
            setRowZeros(0, matrix);
        }
        if (firstCol){
            setColZeros(0, matrix);
        }
    }
    
    private void setColZeros(int col, int[][] matrix){
        for (int i = 0; i < matrix.length; i ++){
            matrix[i][col] = 0;
        }
    }
    
    private void setRowZeros(int row, int[][] matrix){
        for (int i = 0; i < matrix[0].length; i ++){
            matrix[row][i] = 0;
        }
    }    
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: