力扣73题：矩阵置零

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

示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

难度：中等。

算法思路：蛮力，将有0的行和列标记为一个特殊的值，然后再将其变为0，我设置的值是Integer.MIN_VALUE，不过测试样例中输入矩阵中有值为Integer.MIN_VALUE，在160/164个样例被卡了，虽然可以面向测试用例来编程，随便用一个值给标记变量就能过了，不过这确实是一个笨方法。官方题解第二个方法也是这么写的。这里贴一下我的蛮力的程序。

class Solution {
    public void setZeroes(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == 0){
                    for (int k = 0; k < matrix.length; k++) {
                        if(matrix[k][j] != 0){
                            matrix[k][j] = -Integer.MIN_VALUE;
                        }
                    }
                    for (int k = 0; k < matrix[0].length; k++) {
                        if(matrix[i][k] != 0){
                            matrix[i][k] = -Integer.MIN_VALUE;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == -Integer.MIN_VALUE){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
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

在题解区发现了新的算法思路，官方题解居然没有给出来，这个思路来自于作者powcai
算法思路：用matrix第一行和第一列记录该行该列是否有0,作为标志位，不得不说这个想法真是太妙了！这里贴了他的代码。

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        // 第一行是否有零
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        // 第一列是否有零
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }
        // 把第一行第一列作为标志位
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 置0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        } 
    }
}
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

执行用时：
2 ms ,在所有 Java 提交中击败了42.39%的用户
内存消耗：
40.2 MB, 在所有 Java 提交中击败了22.75%的用户