实现算法：矩阵matrix中某个位置为0，则它所在的整行和整列全变0

提示：空间复杂度为o(1)意味着不占用额外空间，或者占用有限个额外空间。
学会用matrix本身做标记，而不是额外空间数组来做标记。

题目

一个矩阵matrix中可能某些位置matrix[i][j]是0，相当于一个炸弹，当你碰到matrix[i][j]=0时，则相应的i行，j列全变0，
要求：空间复杂度为o(1)，请你设计算法实现该算法。

一、审题

看图：

当matrix[i][j] = 0时，让整个i行，整个j列全变零
注意你在遍历过程中需要标记哪些行，哪些列应为全为0，用额外数组，至少需要N+M的外空间
比如造一个col数组，长为M，表示0–M-1列，哪些应该为全0
再造一个row数组，长为N，表示0–N-1行，哪些应该全为0

这样就不是空间复杂度为o(1)了
因此要想别的办法，用matrix的某些地方标记，下面说

二、解题

既然o(1)，我们也要明白，不是一个变量都不用，只要不是大批量用揪心个，偶尔用有限个变量是可以的哦

算法大流程：

1）需要一行，一列，标记，不妨用
0列，整个列标记哪些行变0？
那[0][0]位置就占用来标记0行是否应该全0
故整个0列没法标记了，需要另用一个变量col0来标记0列是否为全0，是就true，否则false
OK，再用整个0行（准确的说，是排除[0][0]位置的 j=1–M-1列）来标记哪些列应该全0

2）有了这些标记，就可以变矩阵了
每次核查，行标记和列标记是否为0，是就改格子为0，不是就不用改了
但是标记的0行，0列，是最后才改的，既然是标记，先把别的地方收拾了
所以从i=N-1行，往i=0上，从下往上变
与此同时，j=0列，作为标记先不动，先j=1从左往右到M-1列变
最后i=0行，由[0][0]位置决定
再最后，j=0列，由col0决定

填表完成！！！没有用额外空间，故空间复杂度为o(1)

代码：

public static int[][] changeToZero(int[][] matrix){
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return null;

        int N = matrix.length;
        int M = matrix[0].length;

        //先遍历标记
        //0行代表j列要不要变0呢？
        //0列代表i行要不要变0呢？
        //col0单独标记0列要变0吗？
        boolean col0 = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                //遇到0操作
                if (matrix[i][j] == 0){
                    matrix[i][0] = 0;//用0列标记i行
                    //另外，单独看看是否这一列是0列，0列用col0标记
                    if (j == 0) col0 = true;
                    else matrix[0][j] = 0;//用0行标记j列
                }
            }
        }

        //做好了标记，o(1)空间复杂度搞定了，一个变量，有限个变量是可以当o(1)的，不是说一个变量都不用
        //按照标记，最后变0行，最后变0列
        for (int i = N - 1; i >= 0; i--) {
            //倒回来填行
            for (int j = 1; j < M; j++) {
                //从左往右填各个格子，但是先不填0列，最后填它
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }
        //最后看0列
        if (col0) for (int i = 0; i < N; i++) {
            matrix[i][0] = 0;//所有的i行0列，全变0
        }

        return matrix;
    }

测试代码：

public static void test(){
        int[][] matrix = {
                {1,2,3,4,5},
                {1,2,0,4,5},
                {1,2,3,4,5},
                {1,2,3,4,5}};
        //显然最后是这样的
//    {1,2,0,4,5},
//    {0,0,0,0,0},
//    {1,2,0,4,5},
//    {1,2,0,4,5}

        matrix = changeToZero(matrix);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        test();
    }

总结

提示：重要知识点：

1）额外空间复杂度为0(1)首先要想到用矩阵本身来做标记
2）额外空间复杂度为0(1)不是一个变量不用，而是可以用有限个变量，这样也是o(1)