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 useextra space? A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still notthe best solution. Could you devise a constant space solution?
Subscribe to see which companiesasked this question.
这一题到最后也只想出了利用O(m+n)的空间来进行求解，就是分别用n和m个长度的数组来记录标识哪一行和哪一列要赋值为0。
然后看了网上别人的代码，发现真的非常巧妙，利用已经找到的0的那一行和那一列来作为额外的开销行和开销列，最后不用额外的空就就能进行求解。
先遍历一遍二维数组，找到1个0，然后记录下这个0所在的行和列的序号，然后利用找到的行和列来作为一个记录数组，记录哪些行哪些列需要赋值为0，最后只需要遍历一次这两个记录数组就可以对原始数组进行赋值，求得解。
1. 遍历1次数组，与0进行比较：
a) 若与0相等，则停止遍历，记录下当前位置的行号x，列号y
b) 若都不与0相等，则直接返回矩阵（说明矩阵中没有0存在）
2. 初始化第x行和第y列为-1；
3. 遍历原始数组，记当前遍历元素为a[i][j]，判断当前元素：
a) 若为0，则a[x][j] = 1 , a[i][y] = 1,表示在x行和y列记录下要赋值为0的行号和列号。
4. 遍历x行和y列，对等于1的行和列进行赋值为0；
class Solution { public: void setZeroes(vector<vector<int>>& a) { if(a.size() < 1)return ; int x,y; int find_zero = 0; x = -1 ; y = -1; for(int i = 0 ; i < a.size() ; i++){ if(find_zero)break; for(int j = 0 ; j < a[0].size() ; j++){ if(a[i][j])continue; find_zero = 1; x = i ; y = j; break; }//for j }//for i if(!find_zero) return; for(int i = 0 ; i < a.size() ; i++)if(a[i][y] != 0) a[i][y] = -1; for(int i = 0 ; i < a[0].size() ; i++)if(a[x][i] != 0) a[x][i] = -1; for(int i = 0 ; i < a.size() ; i++){ for(int j = 0 ; j < a[0].size() ; j++){ if(!a[i][j]){ a[x][j] = 1; a[i][y] = 1; }// end if }//for j }//for i for(int i = 0 ; i < a.size() ; i++) if(a[i][y] == 1 && i != x)a[i].assign( a[0].size(),0); for(int i = 0 ; i < a[0].size() ; i++) if(a[x][i] == 1) for(int k = 0 ; k < a.size() ; k++) a[k][i] = 0; for(int i = 0 ; i < a.size() ; i++)a[i][y] = 0; for(int i = 0 ; i < a[0].size() ; i++)a[x][i] = 0; } };
