将多个集合合并成没有交集的集合
百度面试题：将多个集合合并成没有交集的集合
2010-03-20 18:25
给定一个字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度
（3）请描述可能的改进。
解决方案：
采用hash的方法，key为字符串，value为一个链表，存储集合编号。
算法思想：
用一个数组来存储集合合并关系，如果有N个集合，则用a[N]来存储，元素初始化为-1.
首先，将集合从左往右进行编号：0,1,2,。。。
然后，逐个遍历集合中的字符串，采用hash方法进行映射：先将该集合添加到对应链表中；然后，数组中该集合对应元素如果为-1，则改为链表中最小集合编号，如果不为-1，则不作修改，继续读取下一个字符串，重复该操作。
例如：
{a},{c},{a, b}, {c, d}
分析过程如下：
首先分别编号为0,1,2,3
先读入字符串a:
a 0 [0, -1, -1, -1] // 集合0对应元素原来为-1，故写入编号0
c 1 [0, 1, -1, -1]
a 0,2 [0,1,0,-1] //集合2对应元素原来为-1，故写入该链表中最小编号0
b 2 [0,1,0,-1] //集合2对应元素不为-1，故不做修改
c 1,3 [0,1,0,1]
d 3 [0,1,0,1]
由此，可知0,2为同一集合，1,3为一个集合。
