百度軟件工程師面試題大全(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.anti-gravitydesign.com