中国最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php框架 > 框架设计 > leetcode || 73、Set Matrix Zeroes

leetcode || 73、Set Matrix Zeroes

来源:程序员人生   发布时间:2015-04-30 08:29:00 阅读次数:884次

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; } } };


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生