[LeetCode] Set Matrix Zeroes 解题报告

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(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?

» Solve this problem

[解题思路]
非常无聊的一道题。解题点就在于清空标志位存在哪里的问题。可以创建O(m+n)的数组来存储，但此题是希望复用已有资源。这里可以选择第一行和第一列来存储标志位。

1.先确定第一行和第一列是否需要清零
2.扫描剩下的矩阵元素，如果遇到了0，就将对应的第一行和第一列上的元素赋值为0
3.根据第一行和第一列的信息，已经可以讲剩下的矩阵元素赋值为结果所需的值了
4.根据1中确定的状态，处理第一行和第一列。

[Code]

1:    void setZeroes(vector<vector<int> > &matrix) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      assert(matrix.size()>0);  
5:      int row = matrix.size(), col = matrix[0].size();  
6:      bool zerorow=false, zerocol=false;  
7:      for(int i = 0; i< col; i++)  
8:        if(matrix[0][i] ==0)  
9:          zerorow = 1;  
10:      for(int i = 0; i< row; i++)  
11:        if(matrix[i][0] ==0)  
12:          zerocol=1;  
13:      for(int i =1; i < row; i++)  
14:        for(int j = 1; j<col; j++)  
15:          if(matrix[i][j] ==0)  
16:          {  
17:            matrix[0][j] =0;  
18:            matrix[i][0] =0;  
19:          }  
20:      for(int i =1; i < row; i++)  
21:        for(int j = 1; j<col; j++)  
22:          if(matrix[i][0] ==0 || matrix[0][j] ==0)  
23:            matrix[i][j] =0;  
24:      if(zerorow ==1)  
25:        for(int i =0; i< col; i++)  
26:          matrix[0][i] =0;  
27:      if(zerocol==1)  
28:        for(int i =0; i< row; i++)  
29:          matrix[i][0] =0;          
30:    }