面试题 01.08. 零矩阵

面试题 01.08. 零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2：

输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

void dfs(int **matrix,int n ,int m,int row,int col,int *rrow,int* rcol ){
    
     
     int i;
      // printf("- %d %d ",col,row);
    if(rrow[row]==1){
    
        rrow[row]=0;
                for(i=0;i<m;i++){
    
                    if(matrix[row][i]!=0){
    
                        matrix[row][i]=-999;
                    }
                    else{
    
                        if(rrow[row]==1||rcol[i]==1){
    
                             dfs(matrix,n , m, row, i,rrow,rcol);

                        }
                       
                    }
                }
       }
   if(rcol[col]==1){
    
       rcol[col]=0;
        for(i=0;i<n;i++){
    
            if(matrix[i][col]!=0){
    
                matrix[i][col]=-999;
            }
            else{
    
                  if(rrow[i]==1||rcol[col]==1){
    
                dfs(matrix, n , m, i, col,rrow,rcol);
                  }
            }
        }
   }

}


void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
    
    int n=matrixSize;
    int m=matrixColSize[0];
    int *rrow=(int *)malloc(sizeof(int)*n);
    int *rcol=(int *)malloc(sizeof(int)*m);
    
    int i,j;
    for(i=0;i<n;i++){
    
        rrow[i]=1;
    }
     for(i=0;i<m;i++){
    
        rcol[i]=1;
    }
    printf("df");

    for(i=0;i<n;i++){
    
        if(rrow[i]==1){
    

        for(j=0;j<m;j++){
    
             
            if(matrix[i][j]==0){
    
                       dfs(matrix,n , m, i, j,rrow,rcol);
                       break;
                      }
              }
         }
    }

    for(i=0;i<n;i++){
    
      

        for(j=0;j<m;j++){
    
             
            if(matrix[i][j]==-999){
    
                      matrix[i][j]=0;
                      }
              }
         
    }
}

这里也有一种比较简单的算法，标记出现过0的行和列，然后进行遍历那个那两个存储存储行和列的数组，这种方法就比较简单了