Q: Divide a list of numbers into groups of consecutive numbers but their
original order should be preserved.
Example:
<8,2,4,7,1,0,3,6>
Two groups:
<2,4,1,0,3> <8,7,6>
Algorithm :
We can so this in O(nlogn),if we maintain index along with every element
(copied from google algo group post)
One will be to find the bfs (there will be many and this will lead to
a forest )
This , in turn can be done in O(e+v) , using adjancy list or matrix .
Whenever , we cannot go further , start from any new uncovered node ,
and keep exploring recursively .Keep a boolean flag array for the
elements you have already covered .
Also , this looks like a union find problem .So one can also do this
using disjoint set data structure .
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure
original order should be preserved.
Example:
<8,2,4,7,1,0,3,6>
Two groups:
<2,4,1,0,3> <8,7,6>
Algorithm :
We can so this in O(nlogn),if we maintain index along with every element
(copied from google algo group post)
One will be to find the bfs (there will be many and this will lead to
a forest )
This , in turn can be done in O(e+v) , using adjancy list or matrix .
Whenever , we cannot go further , start from any new uncovered node ,
and keep exploring recursively .Keep a boolean flag array for the
elements you have already covered .
Also , this looks like a union find problem .So one can also do this
using disjoint set data structure .
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure
No comments:
Post a Comment