## Saturday, January 5, 2013

### [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.
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

[解题思路]

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:    }