Problem#

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example#

1
Input:
2
[
3
  [1,1,1],
4
  [1,0,1],
5
  [1,1,1]
6
]
7
Output:
8
[
9
  [1,0,1],
10
  [0,0,0],
11
  [1,0,1]
12
]

1
Input:
2
[
3
  [0,1,2,0],
4
  [3,4,5,2],
5
  [1,3,1,5]
6
]
7
Output:
8
[
9
  [0,0,0,0],
10
  [0,4,5,0],
11
  [0,3,1,0]
12
]

Solution 1#

这道题目特别注重对空间复杂度的控制，最优的解法应当时常数空间。空间开销最大的当属O(mn). 即，遍历一遍矩阵，得到一个mxn的矩阵，其中每一个元素表示matrix上对应位置上的元素是不是应该被置为0.鉴于其过于简单，我们略去其实现。

Solution 2#

在O(mxn)复杂度的基础上，我们可以将复杂度减小至O(m+n). 因为从上一种方法的实现中我们发现，其实我们并不需要记录每一个元素，只需要记录行和列的索引。

1
class Solution {
2
    public void setZeroes(int[][] matrix) {
3
        //O(m_n) space
4
        int [] rows = new int [matrix.length];
5
        int [] cols = new int [matrix[0].length];
6
        for (int i = 0; i < matrix.length; ++i){
7
            for (int j = 0; j < matrix[0].length; ++j){
8
                if (matrix[i][j] == 0){
9
                    rows[i] = 1;
10
                    cols[j] = 1;
11
                }
12
            }
13
        }
14
        for (int i = 0; i < matrix.length; ++i){
15
            if (rows[i] == 1){
16
                for (int j = 0; j < matrix[i].length; ++j){
17
                    matrix[i][j] = 0;
18
                }
19
            }
20
        }
21
        for (int j = 0; j < matrix[0].length; ++j){
22
            if (cols[j] == 1){
23
                for (int i = 0; i < matrix.length; ++i){
24
                    matrix[i][j] = 0;
25
                }
26
            }
27
        }
28
    }
29
}

Solution 3#

有没有常数复杂度的实现呢？我很自然地想到了位运算。但是因为最大只能接受64x64地矩阵作为输入，所以失败了。在看到被人地题解后恍然大悟。O(1)的复杂度自然要求我们把信息存入到矩阵中。我们不妨征用matrix[0][…]和matrix[…][0]作为记录matrix[1..m][1…n]的置零信息。至于第0列行第0行，我们只需要2个单独的变量即可。

1
class Solution {
2
    public void setZeroes(int[][] matrix) {
3
        int row = 0;
4
        int col = 0;
5
        for (int i = 0; i < matrix.length; ++i){
6
            for (int j = 0; j < matrix[i].length; ++j){
7
                if (matrix[i][j] == 0){
8
                    if (i == 0 && col == 0) col = 1;
9
                    if (j == 0 && row == 0) row = 1;
10
                    matrix[i][0] = 0;
11
                    matrix[0][j] = 0;
12
                }
13
            }
14
        }
15
        for (int i = 1; i < matrix.length; ++i){
16
            for (int j = 1; j < matrix[i].length; ++j){
17
                if (matrix[0][j] == 0 | matrix[i][0] == 0) matrix[i][j] = 0;
18
            }
19
        }
20
        if (row == 1){
21
            for (int i = 0; i < matrix.length; ++i){
22
                matrix[i][0] = 0;
23
            }
24
        }
25
        if (col == 1){
26
            for (int i = 0; i < matrix[0].length; ++i){
27
                matrix[0][i] = 0;
28
            }
29
        }
30
    }
31
}