百度软件工程师面试题大全(4)

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

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

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

　　题目中的例子：

　　0:{aaabbbccc}

　　1:{bbbddd}

　　2:{eeefff}

　　3:{ggg}

　　4:{dddhhh}

　　生成的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个集合合并到了一起，

原文转自：http://www.ltesting.net