一、题目描述
二、分析
- 首先不要将题目的意思误解为：将所有的集合合并为一个集合，这是错误的理解
- 本题的意思是：
- 将集合进行合并，合并之后可能有1个集合、2个集合或者多个集合
- 然后这些合并的集合相互之间是没有交集的
演示说明
{aaabbbccc}{bbbddd}{eeefff}{ggg}{dddhhh}
- 然后将多个集合合并成没有交集的集合，最终如下所示：
- 先将有交集的集合都合并到一起
- 然后合并完成之后每个集合之间没有交集
{aaabbbcccdddhhh}{eeefff}{ggg}
三、解决方案
- 集合使用 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 的集合即为最终的集合，它的元素来源于所有直接或 间接指向它的集合
- 算法的复杂度为 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 个集合合并到了一起
四、测试