18 矩阵置0

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

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• $-2^{31}$ <= matrix[i][j] <= $2^{31}$ - 1

进阶：

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

题解1 首行首列做标志记录（原地改数组）

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        const int row = matrix.size();
        const int column = matrix[0].size();
        int flagZeroC(0), flagZeroR(0);
        // 因为后面要置0，所以需要提前记录首行列是否本身含0
        for(auto& i : matrix[0])
            if(! i) 
                flagZeroR = 1;
        for(int i = 0; i < row; i ++){
            if(! matrix[i][0])
                flagZeroC = 1;
        }

        for(int i = 1; i < row; i ++){
            for(int j = 1; j < column; j++){
                if(! matrix[i][j]){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                    // 不能break： 可能还有列需要置0
                }
            }
        }
        // column
        for(int i = 1; i < column; i ++){
            if(! matrix[0][i])
                for(int j = 1; j < row; j++)
                    matrix[j][i] = 0;     
        }
        // row
        for(int i = 1; i < row; i ++){
            if(! matrix[i][0])
                for(int j = 1; j < column; j++)
                    matrix[i][j] = 0;
        }
        // 首行
        if(flagZeroR)
            for(int i = 0; i < column; i ++)
                matrix[0][i] = 0;
        // 首列
        if(flagZeroC)
            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

题解2 位计算

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
    vector<int> row(7,0);
    vector<int> col(7,0);
    int m = matrix.size(),n = matrix[0].size();
    for(int i = 0;i<m;++i)
    {
        for(int j = 0;j<n;++j)
        {
            if(matrix[i][j] == 0)
            {
                row[i/32] |= (1<<(i%32));
                col[j/32] |= (1<<(j%32));
            }
        }
    }
    for(int i = 0;i<m;++i)
    {
        if((row[i/32]>>(i%32))&1)
        {
            for(int j = 0;j<n;++j)
                matrix[i][j] = 0;
        }
    }
    for(int j = 0;j<n;++j)
    {
        if(col[j/32]>>(j%32)&1)
        {
            for(int i = 0;i<m;++i)
                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
28
29
30
31
32
33
34
35