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.

click to show follow up.

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