Thursday, July 17, 2014

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

对于Space: O(m + n)的方法比较好想。主要是O(1)的解法比较有趣,我们把矩阵第一行和第一列当做mark,来判断当前行和列是否需要置0。在这之前需要两个变量先判断矩阵第一行和第一列是否需要置0。
public class Solution {
    //Time: O(m*n)  Space: O(1)
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return;
        }
        //mark first row and col
        boolean zeroFirstRow = false;
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                zeroFirstRow = true;
                break;
            }
        }
        
        boolean zeroFirstCol = false;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                zeroFirstCol = true;
                break;
            }
        }
        
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        //zero
        for (int i = 1; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                zeroRow(matrix, i);
            }
        }
        
        for (int i = 1; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                zeroCol(matrix, i);
            }
        }
        
        if (zeroFirstRow) {
            zeroRow(matrix, 0);
        }
        if (zeroFirstCol) {
            zeroCol(matrix, 0);
        }
    }
    
    private void zeroRow(int[][] matrix, int row) {
        for (int i = 0; i < matrix[0].length; i++) {
            matrix[row][i] = 0;
        }
    }
    
    private void zeroCol(int[][] matrix, int col) {
        for (int i = 0; i < matrix.length; i++) {
            matrix[i][col] = 0;
        }
    }
}

No comments:

Post a Comment