LeetCode 73 Set Matrix Zeroes
题目分析
https://leetcode.com/problems/set-matrix-zeroes/
要解这道题很简单，主要是其限制了要常数的空间复杂度。
空间复杂度 O(mn) 的解法
新建一个同等大小的布尔矩阵，遍历一遍所给的矩阵，如果遇到 0 的话就把其所属行列标记一下。
时间复杂度 O(mn*(m+n))。
空间复杂度 O(m+n) 的解法
新建一个 m+n 的布尔数组，遍历一遍所给的矩阵，如果遇到 0 的话把数组中第 col 个和 n+row 个标记一下。
时间复杂度 O(mn)。
空间复杂度 O(1) 的解法
思路和上面那个解法相似，不过我们直接用所给矩阵的首行和首列来存。
那首行和首列要怎么标记呢？用第一个元素即可。
实际上只用第一个元素是不足以进行标记的，还需要额外一个布尔值，因为首行和首列不是命运共同体， 该点的忽视也导致了我第一次提交 WA。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
bool flag1 = false;
bool flag2 = false;
for(int i=0;i<matrix[0].size();i++) {
if (matrix[0][i] == 0) {
flag1 = true;
break;
}
}
for(int i=0;i<matrix.size();i++) {
if (matrix[i][0] == 0) {
flag2 = true;
break;
}
}
for(int i=1;i<matrix.size();i++) {
for(int j=1;j<matrix[0].size();j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for(int i=1;i<matrix.size();i++) {
for(int j=1;j<matrix[0].size();j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (flag1) {
for(int i=0;i<matrix[0].size();i++) {
matrix[0][i] = 0;
}
}
if (flag2) {
for(int i=0;i<matrix.size();i++) {
matrix[i][0] = 0;
}
}
}
};
时间复杂度 O(mn)。