【第三轮】6.16-6.22 CareerCup 1.7

【解题思路】本来想空间上只有o（1）的，但是发现太麻烦了，就写了一个简化版的，多用空间了
【时间复杂度】O(M*N)
【空间复杂度】O(M+N)
【gist link】https://gist.github.com/jason51122/e03795a0a6bb926aad77

补充内容 (2014-7-2 10:31):
这个空间复杂度其实就是o（1），当时我看错了，不好意思

【解题思路】
     if a[i,j]=0; a[i,0]=0; a[0,j]=0;
   然后
     i>0, j>0时：再遍历a[i,0]和a[0,j]，如果a[..]=0,那么设该行或该列为0
    i=0(j=0)时，check一下是本来就是有零，还是后面设的~如果是前者的话，将该行（or 列）设为全零
【时间复杂度】o(mn)
【空间复杂度】o(m+N)....其实我不懂为啥是这个复杂度...
【gist link】
https://gist.github.com/jaly50/9a2ec0ca4d7d4f31eabf
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
Original matrix is:
  1  4  4
  2  0  8
  1  3  2
  0 21 32

Set zero of the entire row and column:
  0  0  4
  0  0  0
  0  0  2
  0  0  0

【解题思路】遍历matrix找到matrix[i][j] = 0, 标记row[i] col[j] 为True
  python matrix不能直接赋值，先转换成list，坐标转换， 再遍历row[i]or col[j] = True， list对应行列置为0
由于python要转换成list，空间复杂度是不是应该增加？
【时间复杂度】O(M+N)
【空间复杂度】O（M+N）
【gist link】https://gist.github.com/yokiy/cf901aebcace092fdfeb

【解题思路】bool array row[M], col[N] to track;
                  iterate all element to find 0, set corresponding index to bool arrays;
                  based on bool arrays, set row/col to 0
【时间复杂度】O(MN)
【空间复杂度】O(M+N)   can be improved to O(1), still working on it
【gist link】 https://gist.github.com/xun-gong/0138f75595a2986be502

【解题思路】
first scan: search zero elements, keep track of row and column indices
Note:
1. scan twice, first by row then by column, break when meet the first zero since it's enough to know that this row/column should be nullified
2. use dynamically growing vector to hold the row/column indices. (donno how to define bool array with length determined by the size of function parameter...)
second scan: set corresponding rows and columns to zeroIMPROVE:
use first row and column as zero indicator. O(1) space.
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/a6adeac96800415e1dbe
【test case】
M = 0 OR N = 0 -> error reading input
M = 1, N = 1 -> return the original matrix directly
M = 1, N > 1
M > 1, N = 1
other normal cases...

Q: 如何根据parameter的size来定义bool array呀？(C++)
用定义vector<bool>倒是可以，如果想要直接bool[]的话肿么破？matrix.size()不能返回constexpr

【解题思路】
First of all, we cannot immediately set the correspondent cols and rows to zeroes.
Thus try to go through the matrix and record the cols and rows to be set to zeroes, then set them to zeros
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://github.com/FinalF/CarrerUp/blob/master/setZero.java

solution1
Idea: Use two extra boolean array(row[], col[]) to track which row or column has an 0 element.
    1. Scan each element in the matrix, once matrix[j] equals to zero, then set row[i] and col[j] to true[/i][i]
    2. traverse the two boolean array(row[], col[]), if true, set all the elements in the row(or col) to zero
Time Complexity: O(mn) -> O(n^2)
Space Complexity: O(m+n)

solution2
Improve: Just use two extra boolean.
    1. Use two boolean variable to track whether there is an element zero in the first row or col
    2. Use the first row/col to track whether there is an element zero in the matrix(1...length)
Time Complexity: O(mn)
Space Complexity: O(1)

Code is here: http://www.jyuan92.com/post-330
[/i]

【解题思路】
Traverse the two-dimensional array and if the value is 0,
flag its row and column be true. Then traverse the array
again, and set 0 according to flags.
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link】
https://gist.github.com/JoshuaTang/8fe4edf959ae98ab07b9

【解题思路】Use the first row and first colown to record each row's and colown's condition. But first use two additional boolean var to record the condition of first row and colown, since we would change
their value.
【时间复杂度】O(M*N)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/a7cdaac4fd6916993101.git
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
Use the first column and the first row to note whether its related row or column should be set to zero.
Pay attention to the first column and the first row: they should use two extra boolean variables to note whether the first column/row need be set to zero.

【时间复杂度】
O(mn)


【空间复杂度】
O(1)


【gist link】
https://gist.github.com/happyWinner/553704356207ecb21e3f