如何按公共元素合并多组小数组，海量输入下的高效解法是什么

问题所属经典类别 #

该需求属于无向图连通分量划分问题，也是并查集（不相交集合 Union-Find）数据结构的典型应用场景。
我们可以把所有出现过的整数值看作无向图的节点，同一个小数组内的任意两个元素之间存在连接边，最终合并后的每个数组就对应图中的一个连通分量，整个需求等价于找出所有节点的连通分量集合。

大量小数组输入下的优化解法 #

针对大规模输入场景，最优解法是使用带路径压缩、按秩合并的并查集（DSU），针对该场景的实现优化点如下：

• 处理每个小数组时，不需要把数组内元素两两合并，仅需要将数组内所有元素和数组第一个元素执行合并操作即可，可将单个数组的合并操作复杂度从O(n²)降到O(n)
• 路径压缩+按秩合并的优化可以让并查集的查找、合并操作均摊时间复杂度接近O(1)，整体处理效率接近线性
• 如果输入元素取值范围过大、存在稀疏大数值的情况，可以用哈希表代替数组存储并查集的父节点映射，避免无效空间占用
• 所有合并操作完成后，遍历所有出现过的元素，按根节点分组即可得到最终合并后的所有集合。

以题目给出的输入为例：
遍历[0,4]时合并0和4，遍历[1,3]时合并1和3，遍历[3,4]时合并3和4，此时0、1、3、4处于同一个连通分量，遍历[2,5]时合并2和5，最终得到的两个连通分量就是结果[0,1,3,4]、[2,5]，完全符合需求规则，且天然匹配“仅公共元素可合并、区间重叠不作为判断依据”的要求，没有公共元素的数组不会产生连接边，不会被错误合并。

内容的提问来源于stack exchange，提问作者Yaroslav Bres