0821集合问题

{ aaa, bbb, ccc},{bbb, ddd }, { eee, fff }, { ggg },{ddd,hhh} 等一些字符串的集合
要求把交集不为空的集合并起来,如上例会得到 {  aaa, bbb, ccc, ddd, hhh}, {eee,fff},{ggg}
(1) 思想 (2) 算法及复杂度 (3) 改进

 

算法思路：

1. 将每个集合中的元素放到一个HashSet中(方便快速查找)       O(n)

2. 根据每个hashset中元素的个数建最小堆                            O(n)

3. 从堆中取出元素数最少的集合，查找其他HashSet（标志为set1）中是否有与该集合中相同的元素，

       如果有：堆顶hashset与set1进行合并，删除堆顶元素，删除set1，插入合并后的hashset

       如果没有：删除堆顶元素，将其暂存起来 

    如果堆的大小为1时，停止运算                                           O(logn)

 

5. 取出暂存的hashset 和 堆顶hashset, 并打印剩下的hashset  O(n)

 

时间复杂度:

O(n)+O(log(n))

 

算法实现：