题目:
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.(Medium)
分析:
题意很简单,就是把为0的元素所在的行和列都置0;
首先不能直接边循环边做,这样会造成很多本来不是0的元素被置0之后,在后续判断中将它的行列也置0;
所以简单的方法是建立两个数组,存行和列是否为0的情况,遍历一遍更新两个数组,再遍历一遍把应该置0的全部置0。
自己写的时候先考虑用了个set便于不记录重复的下标,所以有如下代码1:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
set<int> rowflag;
set<int> colomnflag;
for (int i = ; i < matrix.size(); ++i) {
for (int j = ; j < matrix[].size(); ++j) {
if (matrix[i][j] == ) {
rowflag.insert(i);
colomnflag.insert(j);
}
}
}
for (auto i : rowflag) {
for (int j = ; j < matrix[].size(); ++j) {
matrix[i][j] = ;
}
}
for (auto i : colomnflag) {
for (int j = ; j < matrix.size(); ++j) {
matrix[j][i] = ;
}
}
return;
}
};
程序还算简洁,记录最坏情况那里空间复杂度是为的O(nlogn + mlogm);
记录bool数组的方式,自己开始觉得写起来不够简洁。
后来看了讨论区大家的写法,发现第二次的用循环一遍,然后rowflag[i] || colonmnflag[j]可以很简洁的写出来,所以有如下代码2:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int rowflag[matrix.size()] = {};
int colomnflag[matrix[].size()] = {};
for (int i = ; i < matrix.size(); ++i) {
for (int j = ; j < matrix[].size(); ++j) {
if (matrix[i][j] == ) {
rowflag[i] = ;
colomnflag[j] = ;
}
}
}
for (int i = ; i < matrix.size(); ++i) {
for (int j = ; j < matrix[].size(); ++j) {
if (rowflag[i] == || colomnflag[j] == ) {
matrix[i][j] = ;
}
}
}
return;
}
};
题目的follow-up中问道能否用常数的空间解决该问题,做法就是用两个变量记录第一行和第一列是否有0,
然后用第一行和第一列充当rowflag,colomnflag即可。