多个集合合并成无交集集合：并查集、哈希映射与排序扫描方案详解

1. 从一个真实的数据清洗场景说起上周帮一个做电商数据的朋友处理用户标签他手里有七八个来源的名单活动报名表、历史订单用户、公众号关注者、线下门店会员、问卷回收名单……每个名单就是一个集合里面存的是用户ID。他想知道的是这些名单之间到底有多少重叠如果要把它们合并成几个互不重叠的组该怎么分这个问题听起来简单但真动手做的时候坑不少。最直觉的做法是两两比对找出所有交集然后把有交集的集合合并。可一旦集合数量上去两两比对的组合数就是 n×(n-1)/2集合一多直接爆炸。更麻烦的是交集关系可能传递——A和B有交集B和C有交集但A和C没有这时候A、B、C应该被合并成同一个组。这就是“将多个集合合并成没有交集的集合”这个问题的核心给定一堆集合把存在重叠关系的集合归并到一起最终输出若干个两两不相交的集合。它在数据清洗、用户去重、权限合并、图连通分量计算等场景里反复出现属于那种“看起来不起眼但绕不过去”的基础算法题。这篇文章我会从思路选型讲到代码落地把并查集、哈希映射、排序扫描几种主流方案都拆开揉碎配上可以直接跑的代码和踩坑记录。不管你是刚接触算法的新手还是想找个靠谱模板直接抄作业的老手应该都能拿到点东西。2. 问题本质与方案选型为什么不能暴力两两比对2.1 先把问题定义清楚输入是一组集合比如[{1,2,3}, {3,4}, {5,6}, {6,7,8}]。输出要求是若干个互不相交的集合且原来任意两个有交集的集合必须落在同一个输出集合里。上面这个例子的正确输出是[{1,2,3,4}, {5,6,7,8}]。注意{1,2,3}和{3,4}因为共享元素 3 被合并{5,6}和{6,7,8}因为共享元素 6 被合并而这两组之间没有任何公共元素所以保持独立。这里有个容易被忽略的点合并具有传递性。如果再加一个{4,9}那么{1,2,3,4}这一组还要继续吸收 9变成{1,2,3,4,9}。所以不能只做一轮两两合并就收工必须保证最终结果里任意两个集合都没有交集。2.2 暴力法的代价有多大最朴素的思路是反复扫描只要发现两个集合有交集就合并直到某一轮没有任何合并发生为止。这个思路正确但复杂度很难看。假设有 n 个集合平均每个集合大小 m。两两比对一次需要 O(m) 时间判断是否有交集用哈希集合一轮下来是 O(n²m)。而最坏情况下可能需要 O(n) 轮才能收敛总复杂度 O(n³m)。n1000 的时候这个量级已经让人不想等了。我早期写过一个版本就是这种暴力合并处理几千个标签集合时跑了十几秒后来换成并查集直接降到毫秒级。这个差距不是优化一点点是数量级的差别。2.3 三种主流方案对比方案核心思想时间复杂度适用场景实现难度并查集把每个元素看作节点同集合元素连边求连通分量O(N·α(N))N为元素总数集合数量多、元素可哈希中等哈希映射归并用元素到组ID的映射边遍历边合并O(N) 近似元素可哈希、内存充足简单排序扫描把元素-集合对排序相邻同元素触发合并O(N log N)元素可比较、内存受限中等三种方案里并查集是最通用也最稳的尤其适合集合数量大、元素类型统一的场景。哈希映射归并写起来最快适合快速脚本。排序扫描则在内存吃紧或者元素本身有序时更有优势。下面我重点讲并查集和哈希映射两种因为它们覆盖了绝大多数实际需求排序扫描作为补充方案在最后提一下。3. 并查集方案把合并问题转成连通性问题3.1 核心思路拆解并查集Union-Find解决这个问题的思路非常优雅不要盯着“集合”这个整体而是盯着“元素”。具体做法是把每个出现过的元素当作一个节点。如果两个元素出现在同一个原始集合里就把它们 union 到一起。等所有原始集合都处理完并查集里的每个连通分量就对应一个最终的合并集合。拿[{1,2,3}, {3,4}, {5,6}, {6,7,8}]举例。处理{1,2,3}时把 1-2、2-3 连起来处理{3,4}时把 3-4 连起来这样 1、2、3、4 就自然连成了一片。处理{5,6}和{6,7,8}同理5、6、7、8 连成另一片。最后按根节点分组输出两个集合。这个转换的妙处在于它把“集合之间是否有交集”这个集合级别的问题降维成了“元素之间是否连通”的节点级别问题而并查集处理连通性正是看家本领。3.2 并查集的实现细节并查集有两个关键优化路径压缩和按秩合并。路径压缩是在 find 的时候把沿途节点直接挂到根上按秩合并是 union 时把矮树挂到高树下。两个一起用单次操作接近 O(1)。class UnionFind: def __init__(self): self.parent {} self.rank {} def add(self, x): if x not in self.parent: self.parent[x] x self.rank[x] 0 def find(self, x): # 路径压缩递归找到根并把沿途节点直接指向根 if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return # 按秩合并矮树挂到高树下避免树退化成链 if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1这里用字典而不是数组来存 parent是因为实际场景里元素往往不是连续的整数可能是字符串ID、UUID 之类。用字典更通用代价是常数稍大但换来的是不用做 ID 到下标的映射。3.3 完整实现与逐行说明def merge_sets_union_find(sets): uf UnionFind() # 第一步把每个集合内的元素两两相连 for s in sets: s list(s) if not s: continue first s[0] uf.add(first) for elem in s[1:]: uf.add(elem) uf.union(first, elem) # 用首元素做锚点减少 union 次数 # 第二步按根节点分组 groups {} for elem in uf.parent: root uf.find(elem) groups.setdefault(root, set()).add(elem) return list(groups.values())第一步里有个小优化值得说不是把集合内所有元素两两 union而是拿第一个元素当锚点其他元素都跟它 union。因为 union 具有传递性union(a,b)加union(a,c)等价于union(a,b)加union(b,c)加union(a,c)但前者少做一次操作。集合大小为 m 时操作次数从 m(m-1)/2 降到 m-1对大连集合很划算。第二步遍历uf.parent的键对每个元素找根按根归组。这里注意要遍历uf.parent而不是原始 sets因为原始 sets 里可能有重复元素而 parent 字典的键天然去重。3.4 复杂度分析与实测数据设所有集合的元素总数为 N去重后为 N并查集的操作次数约为 N 次 find 和 N 次 union配合路径压缩和按秩合并总复杂度 O(N·α(N))α 是反阿克曼函数实际可视为常数。我实测过一组数据10 万个集合每个集合平均 20 个元素元素是 8 位字符串 ID去重后约 150 万个唯一元素。并查集方案在普通笔记本上跑了约 1.8 秒内存占用约 400MB。同样的数据用暴力两两比对跑了 40 多秒还没出结果直接放弃了。注意并查集的性能瓶颈往往不在算法本身而在元素哈希和字典扩容。如果元素是长字符串建议先做一次哈希压缩成整数再进并查集能省不少内存和时间。4. 哈希映射归并写脚本时的快速方案4.1 边遍历边合并的思路如果不想引入并查集那套结构哈希映射归并是更轻量的选择。核心是维护一个元素 - 组ID的映射以及一个组ID - 元素集合的字典。遍历每个原始集合时先看集合里的元素有没有已经归属某个组的。如果都没有就新建一个组如果都归属同一个组直接用如果归属多个不同组就把这些组合并成一个。def merge_sets_hash(sets): elem_to_group {} # 元素 - 组ID groups {} # 组ID - 元素集合 next_gid 0 for s in sets: # 找出这个集合涉及的所有已有组 related set() for elem in s: if elem in elem_to_group: related.add(elem_to_group[elem]) if not related: # 全新的一组 gid next_gid next_gid 1 groups[gid] set(s) for elem in s: elem_to_group[elem] gid elif len(related) 1: # 只涉及一个已有组直接并入 gid related.pop() groups[gid].update(s) for elem in s: elem_to_group[elem] gid else: # 涉及多个组需要合并 gid_list list(related) keep gid_list[0] for other in gid_list[1:]: groups[keep].update(groups[other]) for elem in groups[other]: elem_to_group[elem] keep del groups[other] groups[keep].update(s) for elem in s: elem_to_group[elem] keep return list(groups.values())4.2 合并多个组时的坑上面代码里related有多个组的情况是最容易出 bug 的地方。合并的时候要记得两件事一是把被合并组的元素全部重新指向保留组二是把被合并组从 groups 里删掉。漏了任何一步后面遍历就会拿到脏数据。我见过一个实现漏了更新elem_to_group结果后续集合判断归属时指向了已经删除的组ID直接 KeyError。这种 bug 在小数据上不一定触发数据一多就冒出来排查起来很烦。4.3 与并查集的取舍哈希映射归并的复杂度也是近似 O(N)但常数比并查集小代码也更直观。它的短板在于当合并频繁发生时groups[other]的遍历和elem_to_group的更新会带来额外开销最坏情况下可能退化。我的经验是如果集合之间重叠很少用哈希映射归并更快更简单如果重叠很多、合并频繁并查集更稳。判断标准可以看“平均每个元素出现在几个集合里”这个值大于 2 就倾向并查集。5. 排序扫描方案内存受限时的备选5.1 把元素-集合对排序排序扫描的思路是生成所有(元素, 集合下标)对按元素排序。排序后同一个元素的记录会挨在一起如果某个元素出现在多个集合里这些集合就应该合并。def merge_sets_sort(sets): pairs [] for idx, s in enumerate(sets): for elem in s: pairs.append((elem, idx)) pairs.sort() uf UnionFind() for i in range(len(sets)): uf.add(i) i 0 while i len(pairs): j i # 找到所有相同元素的记录 while j len(pairs) and pairs[j][0] pairs[i][0]: j 1 # 这些记录对应的集合全部 union for k in range(i 1, j): uf.union(pairs[i][1], pairs[k][1]) i j groups {} for idx in range(len(sets)): root uf.find(idx) groups.setdefault(root, set()).update(sets[idx]) return list(groups.values())5.2 适用场景与代价这个方案的优势是内存可控排序可以外部做不需要一次性把所有元素塞进哈希表。代价是 O(N log N) 的排序开销比哈希方案慢一些。它适合元素本身可比较、且内存吃紧的场景。比如处理超大规模的日志数据元素是时间戳或有序ID排序几乎免费这时候排序扫描反而比哈希更快。提示如果元素是整数且范围不大可以用计数排序替代比较排序把复杂度降到 O(N)但要注意元素范围别为了省事开一个巨大的数组。6. 实操中的常见问题与排查技巧6.1 空集合和单元素集合怎么处理空集合直接跳过它不参与任何合并也不应该出现在结果里。单元素集合正常处理它可能通过这个元素和其他集合合并。有个细节如果输入里全是空集合输出应该是空列表而不是包含空集合的列表。我见过有实现把空集合也塞进结果导致下游拿到一堆空集白白增加处理负担。6.2 元素不可哈希怎么办并查集和哈希映射都依赖元素可哈希。如果元素是列表、字典这类不可哈希的对象需要先转成可哈希的形式比如元组、frozenset或者生成一个稳定的字符串表示。转的时候要小心str(dict)的结果依赖键的插入顺序不同顺序的相同字典会得到不同字符串导致本该合并的没合并。稳妥做法是用json.dumps(obj, sort_keysTrue)或者自己写一个规范化函数。6.3 结果集合的顺序问题并查集和哈希映射输出的集合顺序都不确定因为字典遍历顺序依赖哈希。如果下游对顺序有要求需要额外排序。排序键可以选集合的最小元素或者集合大小看业务需求。我一般会在返回前对结果做一次排序按集合内元素排序后的元组比较保证输出稳定方便测试和对比。6.4 常见问题速查表问题现象可能原因排查方向结果里集合数量偏多该合并的没合并检查 union 是否漏调元素是否被错误哈希结果里集合数量偏少不该合并的合并了检查元素哈希是否碰撞字符串表示是否稳定运行超时用了暴力两两比对换成并查集或哈希映射内存爆掉一次性加载所有数据改用排序扫描或分批处理结果不稳定字典遍历顺序输出前对结果排序KeyError合并后没更新映射检查被合并组的元素是否全部重指向6.5 几个我踩过的坑第一个坑是元素类型混用。有一次输入里既有整数1又有字符串1在 Python 里它们哈希不同被当成两个元素结果本该合并的集合没合并。后来我在入口加了一层类型规范化统一转成字符串。第二个坑是并查集初始化遗漏。union 之前必须先 add否则 find 会 KeyError。我图省事在 union 里自动 add结果 rank 字典没同步初始化按秩合并时又出问题。后来老老实实在遍历时先 add 再 union。第三个坑是结果集合去重。如果原始输入里有完全重复的集合并查集方案天然去重因为元素相同就连到一起但哈希映射方案如果没处理好可能生成两个内容相同的组。这个要在合并逻辑里保证。7. 性能优化与扩展思路7.1 分批处理超大规模数据数据量特别大时一次性加载所有集合不现实。可以分批读入每批做一次局部合并最后把各批的结果再合并一次。因为合并操作满足结合律分批不影响最终结果。分批的粒度要权衡批太小中间结果多最后合并开销大批太大内存吃紧。我一般按可用内存的 60% 估算每批能装多少元素留点余量给中间结构。7.2 并行化思路并查集的 union 操作有数据竞争不能直接并行。但可以先把数据分片每片独立建并查集最后合并各片的并查集。合并时把各片的根节点再 union 一次即可。哈希映射归并的并行化更麻烦因为组ID是全局的。一种做法是各片用局部组ID最后做一次全局重映射。这个实现起来复杂除非数据量真的很大否则不建议。7.3 和其他问题的联系这个问题本质上是求无向图的连通分量把每个元素看作节点同集合元素之间连边。所以图论里的连通分量算法DFS、BFS也能用只是建图的内存开销通常比并查集大。它和“区间合并”问题也有相似之处区别在于区间合并依赖有序性而集合合并只依赖元素相等。理解了这个联系遇到变种问题时能更快找到思路。8. 写在最后的一点经验并查集这个结构我一开始觉得它只能做“判断两个元素是否连通”这种题后来发现它在集合合并、图像分割、社交网络分组里到处都是。把“集合合并”转成“元素连通”这个视角的转换是解决这类问题的关键一步值得多体会几次。代码层面我现在的习惯是先用哈希映射归并快速验证逻辑确认结果对了如果性能不够再换并查集。这样能避免一上来就写复杂结构把时间浪费在调试并查集的边界条件上。还有个小技巧测试的时候一定要构造几个“链式合并”的用例比如[{1,2}, {2,3}, {3,4}, {4,5}]这种用例最容易暴露合并传递性没处理好的 bug。单看两两有交集的用例很多错误实现也能蒙混过关。