Set Matrix Zeroes

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?

这道题就是问怎么样储存标志位。因为我们在扫描的时候不能修改matrix,不然扫描出来的结果是修改过的数组,这样就错了,所以我们先扫描一遍,将有0的行和列记录下来,然后再重新将矩阵刷新。如果我们用二维矩阵来记录,肯定是浪费了,如果用一维array也行,最省空间的办法就是用矩阵自己的第一行和第一列来存标志位。
1.先确定第一行和第一列是否需要清零
2.扫描剩下的矩阵元素,如果遇到了0,就将对应的第一行和第一列上的元素赋值为0
3.根据第一行和第一列的信息,已经可以讲剩下的矩阵元素赋值为结果所需的值了
4.根据1中确定的状态,处理第一行和第一列。

public class Solution {
    public void setZeroes(int[][] matrix) {
        boolean firstRowZero = false;
        for (int c = 0; c < matrix[0].length; c++)
        {
            if (matrix[0][c] == 0)
                firstRowZero = true;
        }
        boolean firstColZero = false;
        for(int r = 0; r < matrix.length; r++)
        {
            if (matrix[r][0] == 0)
                firstColZero = true;
        }
        for (int c = 1; c < matrix[0].length; c++)
        {
            for (int r = 1; r < matrix.length; r++)
            {
                if(matrix[r][c] == 0)
                {
                    matrix[0][c] = 0;
                    matrix[r][0] = 0;
                }
            }
        }
        for (int c = 1; c < matrix[0].length; c++)
        {
            if (matrix[0][c] == 0)
            {
                for (int r = 1; r < matrix.length; r++)
                    matrix[r][c] = 0;
            }
        }
        for (int r = 1; r < matrix.length; r++)
        {
            if (matrix[r][0] == 0)
            {
                for (int c = 1; c < matrix[0].length; c++)
                {
                    matrix[r][c] = 0;
                }
            }
        }
        if (firstRowZero)
        {
            for (int c = 0; c < matrix[0].length; c++)
                matrix[0][c] = 0;
        }
        if (firstColZero)
        {
            for(int r = 0; r < matrix.length; r++)
                matrix[r][0] = 0;
        }
    }
}

Second submission:

Remember to deal with first line and row, first record the 0 in the first line and row, than scan the rest of the matrix to record the 0 in the first row and col space, then scan the matrix again to set the 0s according to the info recorded in the first row and col in the previous scan. Finally set the first row and col.

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix.length == 0)
            return;
        //1 row 
        boolean firstRow = false;
        for (int c = 0; c < matrix[0].length; c++) {
            if (matrix[0][c] == 0) {
                firstRow = true;
                break;
            }
        }
        //1 col
        boolean firstCol = false;
        for (int r = 0; r < matrix.length; r++) {
            if (matrix[r][0] == 0) {
                firstCol = true;
                break;
            }
        }
        for (int r = 1; r < matrix.length; r++) {
            for (int c = 1; c < matrix[0].length; c++) {
                if (matrix[r][c] == 0) {
                    matrix[0][c] = 0;
                    matrix[r][0] = 0;
                } 
            }
        }
        
        for (int r = 1; r < matrix.length; r++) {
            if (matrix[r][0] == 0) {
                for (int c = 0; c < matrix[0].length; c++) {
                    matrix[r][c] = 0;
                }
            }
        }
        
        for (int c = 1; c < matrix[0].length; c++) {
            if (matrix[0][c] == 0) {
                for (int r = 0; r < matrix.length; r++) {
                    matrix[r][c] = 0;
                }
            }
        }
        
        if (firstRow) {
            for (int c = 0; c < matrix[0].length; c++) {
                matrix[0][c] = 0;
            }
        }
        
        if (firstCol) {
            for (int r = 0; r < matrix.length; r++) {
                matrix[r][0] = 0;
            }
        }
    }
}

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