四种方法，助你理解 leetcode 73. 矩阵置零_leetcode矩阵置0

题目信息：
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 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]
]
进阶:

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

解题思路
本题要求不使用额外的空间；
方法1： 复制一份矩阵，遍历检索，如果发现为0，则将镜像矩阵的前后左右位置都置为0即可；输出镜像矩阵。该方法使用额外空间

方法2： 申请一维数组，保存为0的行和列信息，第二次遍历修改即可。该方法使用额外空间

方法3： 采用染色法，遍历矩阵，如果发现为0，进行判断，如果前后左右位置之前不为0，则置为定值1（这里取-10000）；如果之前为0，则置为定值2（-20001）；
之后进行第二次遍历，-10000的置为0，-20001的前后左右置为0；

方法4： 采用染色法，遍历矩阵，如果发现为0，将其前后左右不为0的值改为定值；第二次遍历，将所有等于定值的元素设为0；

PS：方法4/3 因为不知道用例的范围，有可能会撞车，建议进行遍历查看一下哪些值没取到

//使用方法3  代码比较冗余，主要看下思路
void setZeroes(int** matrix, int matrixSize, int* matrixColSize){

    //特殊处理

    //第一次处理
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < *matrixColSize; j++) {
            
            //判断是否为0
            if (matrix[i][j] == 0 ) {
                for (int k = 0; k < *matrixColSize; k++) {
                    //特殊场景进行标记
                    if (matrix[i][k] == 0 && k != j) {
                        matrix[i][k] = -10000;
                    } else {
                        matrix[i][k] = -20001;
                    }
                }

                for (int m = 0; m < matrixSize; m++) {
                    //特殊场景进行标记
                    if (matrix[m][j] == 0 && m != i) {
                        matrix[m][j] = -10000;
                    } else {
                        matrix[m][j] = -20001;
                    }
                }
            }
        }
    }

    //第二次处理
    for (int i = 0; i < matrixSize; i++) {
        for (int j = 0; j < *matrixColSize; j++) {
            
            //判断是否为-20001
            if (matrix[i][j] == -20001 ) {
                    matrix[i][j] = 0;
            }
            //判断是否为-10000
            if (matrix[i][j] == -10000 ) {
                for (int k = 0; k < *matrixColSize; k++) {
                    if (matrix[i][k] != -10000 || k == j) {// -10000 防止被冲掉 k == j可以进入
                        matrix[i][k] = 0;
                    }
                }

                for (int m = 0; m < matrixSize; m++) {
                    if (matrix[m][j] != -10000 || m == i) {// -10000 防止被冲掉
                        matrix[m][j] = 0;
                    }
                }
            }
        }
    }
    return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59