返回
29
07/2015

[LeetCode] Set Matrix Zeroes

分类： c/c++, oj | 浏览 (3151) | 评论 (0)

Set Matrix Zeroes

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

click to show follow up.

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?

解题思路：

这道题的题意是，对于矩阵matrix，若matrix[i][j]=0，那么将该行该列都置为0。注意更改后的0不作为0的判别标准。

因此，我们需要记录所有需要清零的行列。

题目要求空间复杂度为O(1)。

解法1：我们先不考虑空间复杂度的情况，用两个set分别记录需要清零的行和列，则有：

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
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m==0){
            return;
        }
        int n = matrix[0].size();
        if(n==0){
            return;
        }
        set<int> zeroRow;
        set<int> zeroCol;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]==0){
                    if(zeroRow.find(i)==zeroRow.end()){
                        zeroRow.insert(i);
                    }
                    if(zeroCol.find(j)==zeroCol.end()){
                        zeroCol.insert(j);
                    }
                }
            }
        }
        for(set<int>::iterator it = zeroRow.begin(); it!=zeroRow.end(); it++){
            for(int i=0; i<n; i++){
                matrix[*it][i] = 0;
            }
        }
        for(set<int>::iterator it = zeroCol.begin(); it!=zeroCol.end(); it++){
            for(int i=0; i<m; i++){
                matrix[i][*it] = 0;
            }
        }
    }
};

解法2：其实我们可以用两个bool数组来记录，对上述代码稍作修改，得到：

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
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m==0){
            return;
        }
        int n = matrix[0].size();
        if(n==0){
            return;
        }
        vector<bool> row(m, false);
        vector<bool> col(n, false);
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]==0){
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for(int i=0; i<m; i++){
            if(row[i]){
                for(int j=0; j<n; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        for(int i=0; i<n; i++){
            if(col[i]){
                for(int j=0; j<m; j++){
                    matrix[j][i] = 0;
                }
            }
        }
    }
};

解法3：上述两种方法的空间复杂度为O(m+n)。要达到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
57
58
59
60
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m==0){
            return;
        }
        int n = matrix[0].size();
        if(n==0){
            return;
        }
        bool firstRow = false, firstCol = false;    //第一行和第一列是否需要置为0
        for(int i=0; i<m; i++){
            if(matrix[i][0] == 0){
                firstCol = true;
                break;
            }
        }
        for(int j=0; j<n; j++){
            if(matrix[0][j] == 0){
                firstRow = 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 i=1; i<m; i++){
            if(matrix[i][0]==0){
                for(int j=1; j<n; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        for(int j=1; j<n; j++){
            if(matrix[0][j]==0){
                for(int i=1; i<m; i++){
                    matrix[i][j] = 0;
                }
            }
        }
        if(firstRow){
            for(int j=0; j<n; j++){
                matrix[0][j] = 0;
            }
        }
        if(firstCol){
            for(int i=0; i<m; i++){
                matrix[i][0] = 0;
            }
        }
    }
};


« [LeetCode] Minimum Path Sum
[LeetCode] Combinations »

0 条评论

    暂无评论。

    发表评论

    电子邮件地址不会被公开。 必填项已用 * 标注