數(shù)組相關元素設為0問題

原問題中垦江，提到了讓我們盡量的減少 space 的使用。這個是我們算法優(yōu)化的方向比吭。

分析

問題需要將將2維數(shù)組中的0元素的同行同列都設為0。如果不涉及 extra space 的話吧慢，可以直接申請另外一個同等大小的 二維數(shù)組來做赏表，非常直觀检诗，但是這里由于有這個 extra space 要求，所以需要換一種方法悠轩。

思路

具體的思路呢，有點像之前的 Unique_Path 問題火架。就是說把首行首列和其他元素分開來處理忙菠，因為這里我們需要 把首行首列元素當做標志位，用來標志該行/列是否需要 set zero牛欢。
所以做法就分三步：

• 先處理首行首列，看首行首列是否含0氢惋，這里用兩個 extra flag 來指定
• 處理其他元素，如果為0骚亿，將相應的首行首列元素置為0，
• 現(xiàn)在首行首列變成了標志位来屠，遍歷剩下的元素震鹉，通過標志位將其他元素置0俱笛。同時根據(jù) extra flag 把首行首列置0

代碼

package day_21;

import java.util.Set;

public class SetZeros {
    public void setZeros(int[][] matrix){
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        int row = matrix.length, col = matrix[0].length;
        int flag_row = 0, flag_col=0;
        for(int i=0;i<col;i++){ // first row
            if(matrix[0][i]==0)
            {flag_row = 1;
            break;}
        }
        for(int i=0;i<row;i++){ // first col
            if(matrix[i][0]==0){
                flag_col=1;
                break;
            }
        }
        for(int i=1;i<row;i++){ // set the first row & col
            for(int j=1;j<col;j++){
                if (matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        for(int i=1;i<col;i++){ // 注意這里的第一行和第一列是由兩個標志位管的
            if(matrix[0][i]==0){
                for(int j=1;j<row;j++){
                    matrix[j][i]=0;
                }
            }
        }

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

        if(flag_row==1){ // 0 is in the first row
            for(int i=0;i<col;i++){
                matrix[0][i]=0;
            }
        }
        if(flag_col==1){ // 0 is in the first col
            for(int i=0;i<row;i++){
                matrix[i][0]=0; 

            }
        }


    }

    public static void main(String args[]){
        SetZeros s = new SetZeros();
        int a[][]= {{1,1,1},{1,0,1},{1,1,1}};
        s.setZeros(a);
        for(int i=0;i<a.length;i++){
            for (int j=0;j<a[0].length;j++){
                System.out.print(a[i][j]);}
        }

    }
}