SetMatrix_0问题

数组相关元素设为0问题

原问题中，提到了让我们尽量的减少 space 的使用。这个是我们算法优化的方向。

分析

问题需要将将2维数组中的0元素的同行同列都设为0。如果不涉及 extra space 的话，可以直接申请另外一个同等大小的 二维数组来做，非常直观，但是这里由于有这个 extra space 要求，所以需要换一种方法。

思路

具体的思路呢，有点像之前的 Unique_Path 问题。就是说把首行首列和其他元素分开来处理，因为这里我们需要 把首行首列元素当做标志位，用来标志该行/列是否需要 set zero。
所以做法就分三步：

• 先处理首行首列，看首行首列是否含0，这里用两个 extra flag 来指定
• 处理其他元素，如果为0，将相应的首行首列元素置为0，
• 现在首行首列变成了标志位，遍历剩下的元素，通过标志位将其他元素置0。同时根据 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]);}
        }

    }
}