请编写一个算法,若N阶方阵中某个元素为0,则将其所在的行与列清零。
给定一个N阶方阵int[][](C++中为vector<>[[1,2,3],[0,1,2],[0,0,1]]
返回:[[0,0,3],[0,0,0],[0,0,0]]
链接:https://www.nowcoder.com/questionTerminal/c95aac1506574dfc8ad44c3939c6739d
来源:牛客网思路1,就是采用两个bool型数组,记录下有0 的行和列。然后分别清除行和列。
时间复杂度0(n^2),但是遍历了两遍,空间复杂度0(n);
下面的方法2,空间复杂度进一步降低,只要两个变量解决问题,空间复杂度0(1)。*/
class
Clearer {
public
:
vector<vector<
int
> > clearZero(vector<vector<
int
> > mat,
int
n) {
// write code here
if
(mat.size()<=0)
return
mat;
//记录行和列的0
bool
* row=
new
bool
[mat.size()];
bool
* col=
new
bool
[mat[0].size()];
//初始化一下
for
(unsigned
int
i=0;i<mat.size();i++)
row[i]=
false
;
for
(unsigned
int
i=0;i<mat[0].size();i++)
col[i]=
false
;
//第一遍遍历元素,统计并标记0的行、列;
for
(unsigned
int
i=0;i<mat.size();i++)
{
for
(unsigned
int
j=0;j<mat[0].size();j++)
{
if
(mat[i][j]==0)
{
row[i]=
true
;
col[j]=
true
;
}
}
}
//对应的位置置为0
for
(unsigned
int
i=0;i<mat.size();i++)
{
for
(unsigned
int
j=0;j<mat[0].size();j++)
{
if
(row[i]||col[j])
mat[i][j]=0;
}
}
return
mat;
}
};
联系客服