leetcode || 73、Set Matrix Zeroes
来源：程序员人生 发布时间：2015-04-30 08:29:00 阅读次数：3060次
problem：
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Hide Tags
Array
题意：矩阵出现0，则将转业和该列置0，注意不要讲矩阵全部置0
thinking：
（1）这道题的实现不难，难在怎样样控制空间复杂度
（2）空间复杂度为O（m*n）的方法不谈，太简单了。空间复杂度为O（m+n）的方法也容易实现，单独开两个数组记录行和列
（3）重点介绍 空间复杂度为 O（1）的方法：
这里只使用两个BOOL 变量便可弄定
1、bool flag_row、 flag_col分别记录首行和首列是不是有0
2、从第2行和第2列开始遍历，如果出现0，则将首行和首列的对应位置 置0
3、2第2步完成以后，也是从第2行和第2列开始根据首行和首列信息填充0；
4、根据第1步的信息填充首行和首列
该方法是利用首行和首列来保存信息，注意首行和首列要单独处理。
code：
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
if(matrix.size()==0)
return;
int m=matrix.size();
int n=matrix[0].size();
bool flag_row=false;
bool flag_col=false;
/*先斟酌单列或单行的特殊情况*/
if(m==1)
{
bool flag=false;
for(int i=0;i<n;i++)
if(matrix[0][i]==0)
flag=true;
if(flag)
{
for(int i=0;i<n;i++)
matrix[0][i]=0;
}
return;
}//m==1
if(n==1)
{
bool flag=false;
for(int i=0;i<m;i++)
if(matrix[i][0]==0)
flag=true;
if(flag)
{
for(int i=0;i<m;i++)
matrix[i][0]=0;
}
return;
}//n==1
for(int i=0;i<m;i++)//第1列是不是有0，记录
{
if(matrix[i][0]==0)
{
flag_col=true;
break;
}
}
for(int j=0;j<n;j++)//第1行是不是有0，记录
{
if(matrix[0][j]==0)
{
flag_row=true;
break;
}
}
for(int i=1;i<m;i++) //从第2行第2列开始，如果出现0，将第1行和第1列的对应位置置0
for(int j=1;j<n;j++)
{
if(matrix[i][j]==0)
{
matrix[0][j]=0;
matrix[i][0]=0;
}
}
for(int i=1;i<m;i++)//逐行检查置0
{
if(matrix[i][0]==0)
{
for(int j=1;j<n;j++)//从第2列开始
matrix[i][j]=0;
}
}
for(int j=1;j<n;j++)//逐列检查，从第2行开始
{
if(matrix[0][j]==0)
{
for(int i=1;i<m;i++)
matrix[i][j]=0;
}
}
if(flag_col) //检查第1列
{
for(int i=0;i<m;i++)
matrix[i][0]=0;
}
if(flag_row) //检查第1行
{
for(int j=0;j<n;j++)
matrix[0][j]=0;
}
}
};
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
