题目：矩阵置零
比较暴力的方法就是：额外使用一个m*n的矩阵，接着对原矩阵进行遍历，每次遇到零都将额外的矩阵中对应的行列置为零——时间和空间复杂度都为O(n^2)
不过我们可以使用更简单的方法
思路如下：
将第一行和第一列作为我们判断的标准，如果 martix[i][j] 为零，那么就相应地将 matrix[i][0] 和 matrix[0][j] 置为零。之后再通过一次遍历，如果 matrix[i][0] 和 matrix[0][j] 其中有一者为零，那么 _martix[i][j] _也等于零
但是这样会导致一个错误，比如说，当第一行全为1，第一列全为0（除了matrix[0][0])时，matrix[0][0]会因为所在列存在零，而被置为零，从而导致第二次遍历时，第一行的元素因为所在行存在零而全被置为0，进而导致整个矩阵全部都为零
为了解决这个问题，我们需要提前知道第一行和第一列的情况，并单独对他们进行处理；
- 所以先遍历第一行和第一列，看看他们是否含有零；
- 之后再处理除了一行一列的其他行列；
- 最后单独为一行一列赋值
1
2void setZeroes(vector<vector<int>>& matrix)
3
4 {
5
6 const int rows = matrix.size();
7
8 const int cols = matrix[0].size();
9
10 bool row_has_zero = false, col_has_zero = false;
11
12
13
14 ///////////////////////////////////////////////////////////////////////////
15
16 // 先遍历第一行和第一列
17
18 ///////////////////////////////////////////////////////////////////////////
19
20 for(int i = 0; i < cols; i++)
21
22 {
23
24 if(matrix[0][i] == 0) row_has_zero = true;
25
26 }
27
28
29
30 for(int i = 0; i < rows; i++)
31
32 {
33
34 if(matrix[i][0] == 0) col_has_zero = true;
35
36 }
37
38
39
40 ///////////////////////////////////////////////////////////////////////////
41
42 // 再处理除了一行一列的其他行列（注意是从1开始）
43
44 ///////////////////////////////////////////////////////////////////////////
45
46 for(int i = 1; i < rows; i++)
47
48 {
49
50 for(int j = 1; j < cols; j++)
51
52 {
53
54 if(matrix[i][j] == 0)
55
56 matrix[0][j] = matrix[i][0] = 0;
57
58 }
59
60 }
61
62
63
64 for(int i = 1; i < rows; i++)
65
66 {
67
68 for(int j = 1; j < cols; j++)
69
70 {
71
72 if(matrix[0][j] == 0 || matrix[i][0] == 0)
73
74 matrix[i][j] = 0;
75
76 }
77
78 }
79
80
81
82 ///////////////////////////////////////////////////////////////////////////
83
84 // 最后为一行一列赋值
85
86 ///////////////////////////////////////////////////////////////////////////
87
88 if(row_has_zero)
89
90 {
91
92 for(int i = 0; i < cols; i++)
93
94 matrix[0][i] = 0;
95
96 }
97
98 if(col_has_zero)
99
100 {
101
102 for(int i = 0; i < rows; i++)
103
104 matrix[i][0] = 0;
105
106 }
107
108 }