[第二轮] 2/18-2/24 CareerCup 1.7

ryancooper 发表于 2013-2-18 07:26
Your idea is nice, but you do a lot of redundant works. In your code, you unnecessarily record too ...

I come up with an idea which is similar to your solution but require only one extra arry to record column information, which is as below:
Traverse through the matrix and keep a boolean flag to mark if there is any element equal to zero in this row, and record column information as you did. Here is the trick, when we switch the row, ie. move from one row to the next, we immediatly set the last row to zero if the flag is true because we do not have to keep the last row any more. Then we only need one boolean variable to keep row information instead of an array. There is no difference in terms of run-time performance, but we have less space overhead.

Here is my solution: https://gist.github.com/czhoume/4975058

mark col number and row number that we need to set to zero in 2 boolean array and traverse the 2 array and set the corresponding col and row to 0.

zuohr 发表于 2013-2-18 10:33
I come up with an idea which is similar to your solution but require only one extra arry to reco ...

Yeah, we can do that. Your improvement is good

I don't understand the meaning of it? Can it be explained in this way: if one of the elements in this matrix is 0, the whole matrix is 0?

Use a boolean matrix to record zeros and then set zeros.
I think I use too many loops.

https://gist.github.com/lynntian/5001309

Java language
https://gist.github.com/mettaworld/5003802
make two functions which store the locations of zero from origin matrix  and make the affected row and column into zero

https://github.com/ltongrc/CareerCup/blob/master/1.7.java

https://github.com/moophis/careercup/blob/master/1.7.cpp
1. Scan through all elements and flag those with value 0;
2. Set the value of rows and columns with 0 value element 0.

put the (x, y) of a Zero Position into A temp array.
Zero the row and colume one by  one


https://gist.github.com/lazyGoose/5017107

* Method: Hold flags of row and col in two one-dimension arrays,
* set the related elements later.
C language: https://gist.github.com/hukun01/5018306