当前位置: 首页 > 面试 > 正文

百度面试-集合合并

关键字:
1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

百度面试题:将多个集合合并成没有交集的集合

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

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

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

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

集合使用hash_set来表示,这样合并时间复杂度比较低。

1. 给每个集合编号为0,1,2,3…

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

3. 创建一个长度等于集合个数的int数组,表示集合间的合并关系。例如,下标为5的元素值为3,表示将下标为5的集合合并到下标为3的集合中去。

开始时将所有值都初始化为-1,表示集合间没有互相合并。

在集合合并的过程中,我们将所有的字符串都合并到编号较小的集合中去。

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

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

题目中的例子:

0: {aaa bbb ccc}
 
1: {bbb ddd}
 
2: {eee fff}
 
3: {ggg}
 
4: {ddd hhh}

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

aaa: 0[-1, -1, -1, -1, -1]
 
bbb: 0, 1[-1, 0, -1, -1, -1]
 
ccc: 0[-1, 0, -1, -1, -1]
 
ddd: 1, 4[-1, 0, -1, -1, 0]
 
eee: 2[-1, 0, -1, -1, 0]
 
fff: 2[-1, 0, -1, -1, 0]
 
ggg: 3[-1, 0, -1, -1, 0]
 
hhh: 4[-1, 0, -1, -1, 0]

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

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

算法的复杂度为O(n),其中n为所有集合中的元素个数。

哈希表加并差集,先用哈希把字符串转成整数,转换的时候就用并差集来操作求集合的并,建立哈希O(n) 哈希查询O(1) 并差集复杂度不好估计,大概为a*O(1)

本文固定链接: http://www.chepoo.com/baidu-interview-6.html | IT技术精华网

百度面试-集合合并:等您坐沙发呢!

发表评论