C++编程 零矩阵详解

题目链接

题目描述：
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2：

输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

数组标记法

我们可以创建两个标记数组，一个记录行，一个记录列，只要有0就标记一下，最后遍历数组，按照标记位置0。

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

通过代码分析：

时间复杂度为O(M * N)
空间复杂度为O(M + N)

优化空间复杂度

这道题我们还可以不创建额外的空间，直接在原数组的第一行和第一列标记0，然后按照上面的方法置行列为0，但是这里有一个问题：标记在第一行和列会改变原数组，所以在标记之前先记录第一行和列是否有0。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        size_t m = matrix.size();
        size_t n = matrix[0].size();
        bool flag_row = false, flag_col = false;
        // 标记第一行第一列是否有0
        for(size_t i = 0; i < n; i++)
        {
            if(!matrix[0][i])
            {
                flag_row = true;
            }
        }
        for(size_t i = 0; i < m; i++)
        {
            if(!matrix[i][0])
            {
                flag_col = true;
            }
        }
        for(size_t i = 1; i < m; i++)
        {
            for(size_t j = 1; j < n; j++)
            {
                if(!matrix[i][j])
                {
                    matrix[i][0] = matrix[0][j] = 0;// 标记到第一行和列
                }
            }
        }
        for(size_t i = 1; i < m; i++)
        {
            for(size_t j = 1; j < n; j++)
            {
                if(!matrix[i][j])
                {
                    matrix[i][0] = matrix[0][j] = 0;// 标记到第一行和列
                }
            }
        }
        for(size_t i = 1; i < m; i++)
        {
            for(size_t j = 1; j < n; j++)
            {
                if(!matrix[i][0] || !matrix[0][j])
                {
                    matrix[i][j] = 0;
                }
            }
        }
        // 处理第一行和第一列
        if(flag_row)
        {
            for(size_t i = 0; i < n; i++)
            {
                matrix[0][i] = 0;
            }
        }
        if(flag_col)
        {
            for(size_t i = 0; i < m; 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

通过代码分析：

时间复杂度为O(M * N)
空间复杂度为O(1)

再优化(拓展思路)

上面我们是用的第一行和第一列进行的标记，现在我们可以直接用第一列进行标记，只用flag记录第一列是否有0，第一行有为0的情况第一列会解决。
但是这里有一个问题：如果正常遍历，第一行的元素就会被改变，所以我们应该逆着遍历。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool flag_col = false;
        for(int i = 0; i < m; i++)
        {
            if(matrix[i][0] == 0)
            {
                flag_col = true;
            }
            for(int j = 1; j < n; j++)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 倒序遍历
        for(int i = m - 1; i >= 0; i--)
        {
            for(int j = 1; j < n; j++)
            {
                if(!matrix[i][0] || !matrix[0][j])
                {
                    matrix[i][j] = 0;
                }
            }
        }
        if(flag_col)// 处理第一列
        {
            for(int i = 0; i < m; 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

通过代码分析：

时间复杂度为O(M * N)
空间复杂度为O(1)

---

---

纸上得来终觉浅，绝知此事要躬行。