leetcode73.Set Matrix Zeroes

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

当遇到数组中的值时，即将该值所在的行和列全部改为0。

思路一：O(m+n）

这里题目中给出了三种空间复杂度。
第一种是O(mn），也就是新建一个boolean[m][n]的二维数组，如果该行列上值为0，则将其对应位置上的值也设置为0.最后再遍历boolean[][]，将true所在的行列设置为0。但是这种方法不仅boolean[][]中很多值用不到，还会导致重复的0赋值行为，效率很低。
这里给出O(m+n)空间复杂度的方法。新建两个boolean[]数组分别代表该行和该列是否需要清零。然后根据这两个数组的情况对原数组进行赋值。代码如下：

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
public void setZeroes(int[][] matrix) {
    int rowCount = matrix.length;
    if(matrix.length==0){
        return;
    }
    int columnCount = matrix[0].length;
    boolean[] rowIsZero = new boolean[rowCount];
    boolean[] columnIsZero = new boolean[columnCount];
    for(int i = 0 ; i<rowCount ; i++){
        for(int j = 0 ; j<columnCount ; j++){
            if(matrix[i][j]==0) {
                rowIsZero[i] = true;
                columnIsZero[j] = true;
            }
        }
    }
    
    for(int i = 0 ; i<rowCount ; i++){
        for(int j = 0 ; j<columnCount ; j++){
            if(rowIsZero[i] || columnIsZero[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

思路二：O(1)空间复杂度

其实我们可以发现，如果我们将原数组中其中的一行和一列利用了来存储当前行和列的清零情况，还可以节约更多的时间和空间。虽然这意味着牺牲了一点时间性能，但是如果数据量非常庞大的话是非常好的一种实现。代码如下：

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
public void setZeroes2(int[][] matrix) {
    if(matrix==null){
        return;
    }
    
    int m = matrix.length;
    int n = matrix[0].length;
    
    boolean rowHasZero = false;
    boolean colHasZero = false;
    
    for(int i=0; i<n; i++){
        if(matrix[0][i]==0){
            rowHasZero = true;
            break;
        }
    }
    
    for(int i=0; i<m; i++){
        if(matrix[i][0]==0){
            colHasZero = true;
            break;
        }
    }
    
    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            if(matrix[i][j]==0){
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }
    

    
    for(int j=1;j<n; j++){
        if(matrix[0][j]==0){
            nullifyCol(matrix, j, m, n);
        }
    }
    
    for(int i=1; i<m; i++){
        if(matrix[i][0]==0){
            nullifyRow(matrix, i, m, n);
        }
    }
    
    if(rowHasZero){
        nullifyRow(matrix, 0, m, n);
    }
    if(colHasZero){
        nullifyCol(matrix, 0, m, n);
    }
    
}