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

思路：

这题题意不是很清楚。很容易让人觉得置0是“连锁反应”，造成最后每个元素都为0。而实际题目的意思是，只有在原始矩阵中为0的数字才能将相应行列置0。而原本非0的数字，即使由于同行或同列的0元素而被置0了，也不能将它相关的行列置0。即这种置0的操作没有传递性，

1. O(mn)解法：克隆原来的matrix，然后扫描原来的matrix，遇到0，则在克隆版本中将对应的行列置0。
2. O(m+n)解法：用两个bool数组O(n)和O(m)，分别记录每行和每列的是否需要被置0。最后根据这两个数组来置0整个矩阵。
3. O(1)解法：用第0行和第0列来记录第1 ~ m-1行和第1 ~ n-1列是否需要置0。而用两个变量记录第0行和第0列是否需要置0。

O(1)解法如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

class Solution { public: void setZeroes(vector<vector<int> > &matrix) { if(matrix.empty() || matrix[0].empty()) return; int m = matrix.size(), n = matrix[0].size(); // find if the 1st row/col needs to be set as zero bool isFirstRowZero = false; bool isFirstColZero = false; for(int j=0; j<n; j++) { if(matrix[0][j]==0) { isFirstRowZero = true; break; } } for(int i=0; i<m; i++) { if(matrix[i][0]==0) { isFirstColZero = true; break; } } // use 1st row/col to record whether to set each col/row as zero for(int i=1; i<m; i++) { for(int j=1; j<n; j++) { if(matrix[i][j]==0) { matrix[i][0] = matrix[0][j] = 0; } } } // set rows & cols for(int i=1; i<m; i++) { if(matrix[i][0]==0) setRowCol(matrix, i, true); } for(int j=1; j<n; j++) { if(matrix[0][j]==0) setRowCol(matrix, j, false); } // set first row & col if(isFirstRowZero) setRowCol(matrix, 0, true); if(isFirstColZero) setRowCol(matrix, 0, false); } void setRowCol(vector<vector<int>> &matrix, int index, bool isSetRow) { if(matrix.empty() || matrix[0].empty() || index<0) return; int m = matrix.size(), n = matrix[0].size(); if((isSetRow && index>=m) || (!isSetRow && index>=n)) return; if(isSetRow) { for(int j=0; j<n; j++) matrix[index][j] = 0; } else { for(int i=0; i<m; i++) matrix[i][index] = 0; } } };