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

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

Can you explain this problem in detail? I mean, it just requires that an algorithm can achieve this operation? Does this operation have the transitivity?  

yang_cs 发表于 2013-2-17 19:33
Can you explain this problem in detail? I mean, it just requires that an algorithm can achieve this  ...

If this operation have the transitivity, all elements will be zero= =...

So I think you just implement an algorithm to simulate this operation.

check which rows and columns are affected. Then set all elements are at those rows or columns.

https://gist.github.com/njcongtou/4972963

use bitmap to record which positions should be set zero

https://gist.github.com/chrislukkk/4973969

jimwallet 发表于 2013-2-18 03:31
check which rows and columns are affected. Then set all elements are at those rows or columns.

ht ...

Nice. Your idea is similar with ls's, both of you want to record which rows and columns are affected, but your algorithm will run much faster than his.

grassgigi 发表于 2013-2-18 07:07
use bitmap to record which positions should be set zero

https://gist.github.com/chrislukkk/497396 ...

Your idea is nice, but you do a lot of redundant works. In your code, you unnecessarily record too much information. For example, in your "traverse all elements in matrix" part, when you find out that mat[j] is 0, you don't have to set your whole ith row and jth column of your bitmap into zero, because all we need to do is to remember that ith row and jth column of the original matrix are need to be set to 0. So you only need to two 1-dimension array, one is for row information, the other is for column's. That is OK, keep in mind that by using bitmap we should increase efficiency dramatically, usually results in having an algorithm runs in lieanr time. Otherwise, there is no need to use it, right.
For the detail implementation, you can refer to jimwallet's code.

ryancooper 发表于 2013-2-18 07:17
Nice. Your idea is similar with ls's, both of you want to record which rows and columns are affect ...

ye, one dimensional arrays for col and row are neat and elegant, i didn't come up with this thought. Nice!

https://gist.github.com/cqx83/4974349
O(mn)
Need to traverse the whole matrix twice.  Record which rows and columns should be set to 0 in the first time. We need two extra arrays.
And then set all the elements which should be zero to 0.

1. have row and col flag to mark the zeros
2. the 2nd pass will set zero for flaged rows and cols
https://gist.github.com/mazl123321/4974587