// @Title: 矩阵置零 (Set Matrix Zeroes)
// @Author: qisiii
// @Date: 2024-10-13 22:08:14
// @Runtime: 11 ms
// @Memory: 44.7 MB
// @comment: 空间换时间，核心思想是用第0行和第0列来记录当前行列是否有0
// @flag: BLUE
class Solution {
    public void setZeroes(int[][] matrix) {
        //核心思想在于使用矩阵的第一行第一列用于记录matrix[1-m,1-n]范围是否有0，并且需要额外空间来记录第0行和第0列是否有0
        boolean row=false,column=false;
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]==0){
                    if(i==0){
                        row=true;
                    }
                    if(j==0){
                        column=true;
                    }
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }
        //类似于投影的概念
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[0][j]==0||matrix[i][0]==0){
                    matrix[i][j]=0;
                }
            }
        }
        System.out.println(row+" "+column);
        if(row){
            for(int i=0;i<matrix[0].length;i++){
                matrix[0][i]=0;
            }
        }
        if(column){
            for(int i=0;i<matrix.length;i++){
                matrix[i][0]=0;
            }
        }
    }
}

// @Title: 矩阵置零 (Set Matrix Zeroes)
// @Author: qisiii
// @Date: 2024-10-13 21:53:44
// @Runtime: 3 ms
// @Memory: 44.6 MB
// @comment: 额外空间O(m+n)，时间复杂度O(n2)
// @flag: WHITE
class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> rowZeroSet=new HashSet<>();
        Set<Integer> columnZeroSet=new HashSet<>();
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j]==0){
                    rowZeroSet.add(i);
                    columnZeroSet.add(j);
                }
            }
        }
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(rowZeroSet.contains(i)||columnZeroSet.contains(j)){
                    matrix[i][j]=0;
                }
            }
        }
    }
}