首页 > 代码库 > 多个集合合并成没有交集的集合

多个集合合并成没有交集的集合

问题描述                                                                                     

将多个集合合并成没有交集的集合。

给定一个字符串的集合,格式如:{aaa bbb ccc}, {bbb ddd},{eee fff},{ggg},{ddd hhh}要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应输出{aaa bbb ccc ddd hhh},{eee fff}, {ggg}。

(1)请描述你解决这个问题的思路;

(2)请给出主要的处理流程,算法,以及算法的复杂度

(3)请描述可能的改进。

解决方案                                                                                      

采用hash的方法,key为字符串,value为一个链表,存储集合编号。

分析                                                                                            

1. 假定每个集合编号为0,1,2,3...

2. 创建一个hash_map,key为字符串,value为一个链表,链表节点为字符串所在集合的编号。遍历所有的集合,将字符串和对应的集合编号插入到hash_map中去。

3. 创建一个长度等于集合个数的int数组,表示集合间的合并关系。例如,下标为5的元素值为3,表示将下标为5的集合合并到下标为3的集合中去。开始时将所有值都初始化为-1,表示集合间没有互相合并。在集合合并的过程中,如果数组中该集合对应元素如果为-1,则改为链表中最小集合编号,如果不为-1,则不作修改,继续读取下一个字符串。

遍历第二步中生成的hash_map,对于每个value中的链表,首先找到最小的集合编号(有些集合已经被合并过,需要顺着合并关系数组找到合并后的集合编号),然后将链表中所有编号的集合都合并到编号最小的集合中(通过更改合并关系数组)。

4.现在合并关系数组中值相等的集合即为最终的集合,它的元素来源于所有直接或间接指向它的集合。

过程                                                                                           

0: {aaa bbb ccc}

1: {bbb ddd}

2: {eee fff}

3: {ggg}

4: {ddd hhh}

生成的hash_map,和处理完每个值后的合并关系数组分别为

aaa: 0          [0,-1,-1,-1,-1]         

bbb: 0          [0,-1,-1,-1,-1] 

ccc: 0            [0,-1,-1,-1,-1]   

bbb: 0,1        [0, 0,-1,-1,-1] 

ddd: 1           [0, 0,-1,-1,-1]  

eee: 2           [0, 0, 2,-1,-1]  

fff: 2              [0, 0, 2,-1,-1]     

ggg: 3            [0, 0, 2, 3,-1]    

ddd: 1,4         [ 0, 0, 2,3 , 0]  

hhh: 4            [ 0, 0, 2, 3, 0]  

所以合并完后有三个集合,第0,1,4个集合合并到了一起,

第2,3个集合没有进行合并。

我是天王盖地虎的分割线                                                                                   

 

 

参考:http://www.cnblogs.com/ttltry-air/archive/2012/08/14/2638437.html

http://blog.csdn.net/yahohi/article/details/7927233