矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

进阶:

一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

咋一看，这个问题很简单：直接遍历整个矩阵，只要发现值为0的元素，就将其所在的行与列清零。不过这种方法有个缺陷：在读取被清零的行与列时，读到的尽是零，于是所在的行与所在的列都变成了0，很快，整个矩阵都变成了0.

避开这个缺陷的方法之一是新建一个矩阵标记零元素的位置。然后，在第二遍遍历矩阵的时候将0元素所在的行与列清零。这种做法的空间复杂度为O(MN)

真的需要占用O(MN)空间吗？不是的，既然打算将整行和整列清零，因此并不需要标记录它是cell[2][4]（行2，列4），只需要知道行2有个元素为0，列4有个元素为0.不管怎样，整行和整列都要清零，又何必要记录零元素的确切位置？

    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] index = new int[m+n];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]==0){
                    index[i]=1;
                    index[n+j]=1;
                }
            }
        }

        for(int i=0;i<n;i++){
            if(index[i]==1){
                for(int j=0;j<m;j++){
                    matrix[i][j]=0;
                }
            }
        }
        
        for(int j=0;j<m;j++){
            if(index[n+j]==1){
                for(int i=0;i<n;i++){
                    matrix[i][j]=0;
                }
            }
        }
        
    }

常数空间的解决方案：
我们可以使用原矩阵的第一行和第一列来记录哪些行和列需要全部置为0。
首先看第一行和第一列有没有0，如果有，记录flag表示之后第一行或第一列需要全部置为0；
遍历除了第一行和第一列的所有元素，如果元素为0，则将其所在行与第一列交点的元素，其所在列与第一行交点的元素都置为0。
根据第一行和第一列中的0，将其他行列的元素置为0；
根据记录的flag将第一行和第一列置为0。