【第四轮】3.30 -4.5 Career Cup 1.7

解题思路】
// If martix[j] = 0, then martix[i][] = 0 and matrix[][j] = 0        
// We construct two array indicators to log if a row/col should be set to zero[/i][i]【时间复杂度】
* Time complexity: O(m*n)
【空间复杂度】
* Space complexity: O(m+n)
【gist link] https://github.com/bxshi/intervi ... I5/1_7_set_zero.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享） https://github.com/bxshi/intervi ... c/test/1_7_test.cpp[/i]

[solution]
1. use two bool arrays, one to indicate whether a row should be set to zero, another to indicate whether a col should be set to zero.
2. first scan of the matrix to update the two bool arrays.
3. second scan of the matrix to set the correspond elements.
[time]
O(mn)
[space]
O(m+n)
[gist]
https://gist.github.com/kelly-us/9d0af336171822f9c17e

【解题思路】
* First, we at least need two loops, one for finding out the rows and columns containing 0,
* the other one to set 0. We cannot do it in one loop, because it will influence result.
* We set the row and column which contain 0, true.
* Then in the next loop, if row or column is true, we set it 0.
*
* Note: "or" is very important here, think about it. I used three loops initially, which is not most efficient.
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/leonw007/47cf3244fea404e21562
【test case】included in the link above

【解题思路】
可以开一个行数组row和列数组col，当元素a[i][j]等于0时， 就把row[i]和col[j]置为true。第二次遍历矩阵时，当某个元素对应的行row[i] 或列col[j]被设置为true，说明该元素在需要被置0的行或列上，因此将它置0。
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/songpu2015617/46b8ba53f41adb40560a

【解题思路】Two passes: First pass to find the row indexes and column indexes which contain 0 element. Second pass to set the element which lies either in the row indexes or column indexes to zero.
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link]
https://github.com/StephenWeiXu/ ... blob/master/1_7.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享）
https://github.com/StephenWeiXu/ ... blob/master/1_7.cpp

【解题思路】
Tips:
* Use two array to mark which row and which col should be reset to zero perspectively.
* Use the first row and column to mark which row and col should be reset to zero perspectively.
【时间复杂度】1&2. O(M*N)
【空间复杂度】1. O(M+N) 2.O(1)
【gist link】https://github.com/drinkbeer/Cod ... /src/CC150_1_7.java
【test case】

【gist link】github.com/Etherque/Career-Cup/blob/master/setZeros.java"
Time Complexity O(m x n)
Space O(1)