leetcode || 73、Set Matrix Zeroes
來源：程序員人生 發(fā)布時間：2015-04-30 08:29:00 閱讀次數(shù)：3305次
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
題意：矩陣出現(xiàn)0，則將轉(zhuǎn)業(yè)和該列置0，注意不要講矩陣全部置0
thinking：
（1）這道題的實現(xiàn)不難，難在怎樣樣控制空間復雜度
（2）空間復雜度為O（m*n）的方法不談，太簡單了。空間復雜度為O（m+n）的方法也容易實現(xiàn)，單獨開兩個數(shù)組記錄行和列
（3）重點介紹 空間復雜度為 O（1）的方法：
這里只使用兩個BOOL 變量便可弄定
1、bool flag_row、 flag_col分別記錄首行和首列是不是有0
2、從第2行和第2列開始遍歷，如果出現(xiàn)0，則將首行和首列的對應位置 置0
3、2第2步完成以后，也是從第2行和第2列開始根據(jù)首行和首列信息填充0；
4、根據(jù)第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列開始，如果出現(xiàn)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;
}
}
};
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
