## Monday, November 24, 2014

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

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 > &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> &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