leetcode 73. Set Matrix Zeroes (矩阵置0，乱搞)
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存在
1 int cntx=0,cnty=0;
2 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
3 {
4 if (i!=x)
5 for ( int j = 0 ;j < m ; j++)
6 {
7 if (a[i][j]==0)
8 {
9 if (cntx==x)
10 {
11 a[cntx][y] = -1;
12 cntx++;
13 }
14 a[cntx++][y] = i;
15 break;
16 }
17 }
18 }
19 for ( int j = 0 ; j < m ; j++)
20 {
21 if (j!=y)
22 for ( int i = 0 ; i < n ; i++)
23 {
24 if (a[i][j]==0)
25 {
26 if (cnty==y)
27 {
28 a[x][cnty] = -1; // set a mark the (x,y),or the original value 0 will mislead the program.
29 cnty++;
30 }
31 a[x][cnty++] = j ;
32 break;
33 }
34 }
35 }
36 for ( int i = 0 ; i < cntx ; i++)
37 {
38 int XX = a[i][y];
1 if (XX==x||XX==-1) continue;
2 for ( int j = 0 ; j < m ; j++)
3 if (j!=y) // fill the 0 in two steps,ensuring not to cover the info
4 a[XX][j] = 0 ;
5 }
6 for ( int j = 0 ; j < cnty ; j++)
7 {
8 int YY = a[x][j];
9 if (y==YY||YY==-1) continue;
10 // cout<<"YY:"<<YY<<endl;
11 for (int i = 0 ; i < n ; i++)
12 if (i!=x)
13 a[i][YY] = 0;
14 }
15 for ( int i = 0 ; i < n ; i++)
16 for ( int j = 0 ; j < m ; j++)
17 if (i==x||j==y) a[i][j] = 0 ;
18 }
19};
下面有一个更精简的思路：
直接用每一行和每一列的第一个位置记录相应行和相应列的状态（(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();
1 for (int i = 0; i < n; i++) {
2 if (matrix[i][0] == 0) col0 = 0;
3 for (int j = 1; j < m; j++)
4 if (matrix[i][j] == 0)
5 matrix[i][0] = matrix[0][j] = 0;
6 }
1 for (int i = n-1; i >=0 ;i--) {
2 for (int j = m-1; j >=1; j--)
3 if (matrix[i][0] == 0 || matrix[0][j] == 0)
4 matrix[i][j] = 0;
5 if (col0 == 0) matrix[i][0] = 0;
6 }
7 }
8};