Note: This article is available in Chinese only. 本文暂无英文版本。
View original
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
**Follow up:**Did you use extra space? A straight forward solution using O(m__n) 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?
直接放常数空间的做法。
这道题面hypereal的时候遇到过，基本思路就是用已经确定是0的位置来存储其他行和列的信息。
三点注意：
* (x,y)不要放任何信息，不然行和列的信息，后面处理的那个可能被覆盖掉。
* (x,y)位置要进行标记，否则默认的0值可能会造成歧义
* 赋值成0的时候要分成两部分，处理的时候避免因为处理前面赋值成了0，把后面标记的行和列的标号覆盖掉。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月10日 星期一 08时06分27秒
4File Name :73.cpp
5************************************************ */
6class Solution {
7public:
8 void setZeroes(vector<vector<int>>& a) {
9 int n = a.size();
10 int m = a[0].size();
11 bool ok = false;
12 int x,y;
13 x = y = -1;
14 for ( int i = 0 ; i < n ; i++)
15 {
16 if (ok) break;
17 for ( int j = 0 ; j < m; j++)
18 {
19 if (a[i][j]==0)
20 {
21 x = i;
22 y = j;
23 ok = true;
24 break;
25 }
26 }
27 }
28 if (x==-1) return ; //没有0存在
29
30
31 int cntx=0,cnty=0;
32 for ( int i = 0 ; i < n ; i++) // note to avoid the (x,y) to record any info,or it may be coverd by the latter info
33 {
34 if (i!=x)
35 for ( int j = 0 ;j < m ; j++)
36 {
37 if (a[i][j]==0)
38 {
39 if (cntx==x)
40 {
41 a[cntx][y] = -1;
42 cntx++;
43 }
44 a[cntx++][y] = i;
45 break;
46 }
47 }
48 }
49 for ( int j = 0 ; j < m ; j++)
50 {
51 if (j!=y)
52 for ( int i = 0 ; i < n ; i++)
53 {
54 if (a[i][j]==0)
55 {
56 if (cnty==y)
57 {
58 a[x][cnty] = -1; // set a mark the (x,y),or the original value 0 will mislead the program.
59 cnty++;
60 }
61 a[x][cnty++] = j ;
62 break;
63 }
64 }
65 }
66 for ( int i = 0 ; i < cntx ; i++)
67 {
68 int XX = a[i][y];
69
70 if (XX==x||XX==-1) continue;
71 for ( int j = 0 ; j < m ; j++)
72 if (j!=y) // fill the 0 in two steps,ensuring not to cover the info
73 a[XX][j] = 0 ;
74 }
75 for ( int j = 0 ; j < cnty ; j++)
76 {
77 int YY = a[x][j];
78 if (y==YY||YY==-1) continue;
79 // cout<<"YY:"<<YY<<endl;
80 for (int i = 0 ; i < n ; i++)
81 if (i!=x)
82 a[i][YY] = 0;
83 }
84 for ( int i = 0 ; i < n ; i++)
85 for ( int j = 0 ; j < m ; j++)
86 if (i==x||j==y) a[i][j] = 0 ;
87 }
88};下面有一个更精简的思路：
直接用每一行和每一列的第一个位置记录相应行和相应列的状态（(0,0)点会有重合，再加一个变量记录就好）
得到信息后记得从右下角往左上更新，避免信息覆盖。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月10日 星期一 08时06分27秒
4File Name :73.cpp
5************************************************ */
6class Solution {
7public:
8 void setZeroes(vector<vector<int> > &matrix) {
9 int col0 = 1, n = matrix.size(), m = matrix[0].size();
10
11 for (int i = 0; i < n; i++) {
12 if (matrix[i][0] == 0) col0 = 0;
13 for (int j = 1; j < m; j++)
14 if (matrix[i][j] == 0)
15 matrix[i][0] = matrix[0][j] = 0;
16 }
17
18 for (int i = n-1; i >=0 ;i--) {
19 for (int j = m-1; j >=1; j--)
20 if (matrix[i][0] == 0 || matrix[0][j] == 0)
21 matrix[i][j] = 0;
22 if (col0 == 0) matrix[i][0] = 0;
23 }
24 }
25};