首页 > 代码库 > [LeetCode]73 Set Matrix Zeroes

[LeetCode]73 Set Matrix Zeroes

https://oj.leetcode.com/problems/set-matrix-zeroes/

http://blog.csdn.net/linhuanmars/article/details/24066199

public class Solution {
    public void setZeroes(int[][] matrix)
    {
        // Solution A:
        // setZeroes_NoExtraSpace(matrix);
        
        // Solution B:
        setZeroes_ExtraRowAndCol(matrix);
    }
    
    ////////////////////////
    // Solution A: NoExtraSpace
    //
    // 使用第一行和第一列来记录
    private void setZeroes_NoExtraSpace(int[][] matrix)
    {
        if (matrix == null)
            return;
        
        // Assume it is m * n;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        // Handle first row
        boolean firstRow0 = false;
        for (int i = 0 ; i < n ; i ++)
        {
            if (matrix[0][i] == 0)
            {
                firstRow0 = true;
            }
        }
        
        // First col
        boolean firstCol0 = false;
        for (int i = 0 ; i < n ; i ++)
        {
            if (matrix[0][i] == 0)
            {
                firstCol0 = true;
            }
        }
        
        for (int i = 1 ; i < m ; i ++)
        {
            for (int j = 1 ; j < n ; j ++)
            {
                if (matrix[i][j] == 0)
                {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        for (int i = 0 ; i < m ; i ++)
        {
            for (int j = 0 ; j < n ; j ++)
            {
                if (i == 0 && firstCol0)
                {
                    matrix[i][j] = 0;
                }
                else if (j == 0 && firstRow0)
                {
                    matrix[i][j] = 0;
                }
                else if (i > 0 && j > 0 && (matrix[0][j] == 0 || matrix[i][0] == 0))
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
    
    
    ////////////////////////
    // Solution B: ExtraRowAndCol
    //
    private void setZeroes_ExtraRowAndCol(int[][] matrix)
    {
        if (matrix == null)
            return;
        
        // Assume it is m * n;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        boolean[] cols = new boolean[m];
        boolean[] rows = new boolean[n];
        
        for (int i = 0 ; i < m ; i ++)
        {
            for (int j = 0 ; j < n ; j ++)
            {
                if (matrix[i][j] == 0)
                {
                    cols[i] = true;
                    rows[j] = true;
                }
            }
        }
        
        for (int i = 0 ; i < m ; i ++)
        {
            for (int j = 0 ; j < n ; j ++)
            {
                if (cols[i] || rows[j])
                    matrix[i][j] = 0;
            }
        }
    }
}


[LeetCode]73 Set Matrix Zeroes