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?

思路

參考http://www.voidcn.com/article/p-nodlrltb-bdw.html

方案一： 用2個(gè)extra array來(lái)記錄該行該列是否需要設(shè)置為0

使用兩個(gè)數(shù)組來(lái)標(biāo)記某一行或是某一列是否存在 0。這是一種 O(m + n) 空間復(fù)雜度的實(shí)現(xiàn)方式。

共3次循環(huán)

1. 第一次循環(huán)，設(shè)置這2個(gè)數(shù)組的flag
2. 第二次循環(huán)，根據(jù)rowFlgArray設(shè)置矩陣的行為0
3. 第三次循環(huán)，根據(jù)colFlgArray設(shè)置矩陣的列為0

class Solution {
    public void setZeroes(int[][] matrix) {
        /* solution 1**********************
        //SOLUTION1. O(m + n)的方法，有2個(gè)數(shù)組，分別記錄該行和該列是否需要設(shè)置為0
        if (matrix == null || matrix[0].length == 0 || matrix.length == 0) {
            return;
        }
        
        int row = matrix.length;
        int col = matrix[0].length;
        
        int[] rowFlg = new int[col];
        int[] colFlg = new int[row];
        
        //1. 設(shè)置flg
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    colFlg[i] = 1;
                    rowFlg[j] = 1;
                }
            }
        }
        
        //3. 根據(jù)flg設(shè)置row zeros
        for (int i = 0; i < row; i++) {
            if (colFlg[i] == 1) {
                for (int j = 0; j < col; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        //4. 根據(jù)flg設(shè)置col zeros
        for (int i = 0; i < col; i++) {
            if (rowFlg[i] == 1)
            for (int j = 0; j < row; j++) {
                matrix[j][i] = 0;
            }
        }
}

方案二：用第一行 第一列來(lái)存 該行該列是否需要被設(shè)置為0. （不需要extra space）

一共2次遍歷矩陣，+ 2次設(shè)置第一行/第一列為0（Option）

1. 第一次遍歷找出標(biāo)記，設(shè)置第一列和第一行。
2. 第二次遍歷使用標(biāo)記標(biāo)注矩陣，第二遍標(biāo)記的時(shí)候不能把標(biāo)記列（行）本身也遍歷一遍，所以要排除標(biāo)記行和列，從（1，1）開(kāi)始循環(huán)起走，如果碰到第一行和第一列的標(biāo)志位為0，那么將該元素設(shè)置為0。
3. 修正第一列和第一行的其他元素：很簡(jiǎn)單，那么設(shè)置兩個(gè)額外的bool變量告訴第一行和第一列的其他元素是否要變?yōu)?.在第一遍遍歷的時(shí)候如果Matrix[i,j]==0時(shí)i和j為0，那么對(duì)應(yīng)的標(biāo)記就要為true
   流程就是第一遍遍歷全部，找出標(biāo)記；第二遍遍歷除標(biāo)記列（行）意外的元素，將必要的元素置為0.第三次遍歷標(biāo)記列（行），根據(jù)兩個(gè)標(biāo)記考慮是否將其所有元素置為0.

 /* solution 2*********************************************************/
        //用第一行 第一列來(lái)存 該行該列是否需要被設(shè)置為0. 
        //一共兩次循環(huán)，第一次循環(huán)，設(shè)置第一列和第一行
        //第二次循環(huán)，不要循環(huán)第一行和第一列，從（1，1）開(kāi)始循環(huán)起走，如果碰到第一行和第一列的標(biāo)志位為0，那么將該元素設(shè)置為0
        //第一列和第一行如何表示需要全部設(shè)置為0呢？ 在第一次掃描時(shí)，用2個(gè)boolean flag來(lái)標(biāo)識(shí)
        
        if (matrix == null || matrix[0].length == 0 || matrix.length == 0) {
            return;
        }
        
        int row = matrix.length;
        int col = matrix[0].length;
        
        boolean fstRowFlg = false;
        boolean fstColFlg = false;
        
        //1. 第一次循環(huán)
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                    if (i == 0) fstRowFlg = true;
                    if (j == 0) fstColFlg = true;
                }
            }
        }
        
        //2. 第二次循環(huán)，設(shè)置去掉第一行第一列后的數(shù)組為0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        //3. set first row into zeros
        if (fstRowFlg) {
            for (int i = 0; i < col; i++) {
                matrix[0][i] = 0;
            }
        }
        
        //4. set first col into zeros
        if (fstColFlg) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }  
    }