73. 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?
思路: 使用第一行和第一列记录某行或某列是否应置为0,并再用两个状态位分别标记第一行和第一列是否也应该被置为0.

public class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
        int row = matrix.length;
        int col = matrix[0].length;
        boolean isFirstRowSetZero = false;
        boolean isFirstColSetZero = false;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    if (i == 0) isFirstRowSetZero = true;
                    if (j == 0) isFirstColSetZero = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 按照第一列元素结果填充各行
        for (int j = 1; j < col; j++) {
            if (matrix[0][j] == 0 ) {
                for (int i = 0; i < row; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
         //按第一行个元素的记录情况填充各列
        for (int i = 1; i < row; i++) {
            if (matrix[i][0] == 0 ) {
                for (int j = 0; j < col; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (isFirstRowSetZero) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }

        if (isFirstColSetZero) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 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