Python实现合并存在至少一个匹配元素的嵌套列表

嘿，这个问题本质上是找连通分量的问题——把所有存在关联（有共同元素）的子列表合并成一个大集合，用并查集（Union-Find）算法来处理最顺手了！我给你一步步拆解实现思路和代码：

核心思路 #

并查集是专门用来处理这类元素连通性问题的数据结构，核心就是两个操作：

• find：查找某个元素的根节点（代表它所在的集合）
• union：把两个元素所在的集合合并到一起

具体步骤如下：

1. 先给所有出现过的元素初始化父节点，每个元素初始时自己就是自己的父节点
2. 遍历每个子列表，把列表里的所有元素都合并到同一个集合（比如把每个元素和子列表的第一个元素合并）
3. 最后把所有元素按照它们的根节点分组，就能得到合并后的结果

Python 实现代码 #

def merge_overlapping_lists(nested_list):
    # 初始化并查集的父节点映射，每个元素初始父节点是自己
    parent = {}
    
    def find(x):
        # 查找元素x的根节点，同时做路径压缩优化，加快后续查找速度
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        # 合并x和y所在的两个集合
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            # 把一个集合的根节点指向另一个集合的根节点
            parent[root_y] = root_x
    
    # 第一步：给所有元素初始化父节点
    for sublist in nested_list:
        for num in sublist:
            if num not in parent:
                parent[num] = num
    
    # 第二步：合并每个子列表内的元素，让它们属于同一个集合
    for sublist in nested_list:
        if len(sublist) < 2:
            continue  # 单个元素的子列表不需要合并操作
        # 以子列表第一个元素为基准，合并其他所有元素
        base_num = sublist[0]
        for num in sublist[1:]:
            union(base_num, num)
    
    # 第三步：根据根节点对元素分组
    groups = {}
    for num in parent:
        root = find(num)
        if root not in groups:
            groups[root] = []
        groups[root].append(num)
    
    # 返回合并后的列表，若需要子列表内元素有序，可改为 sorted(group)
    return list(groups.values())

# 测试你的输入案例
input_list = [[0, 2], [0, 1], [2, 3], [4, 5, 7, 8], [6, 4]]
print(merge_overlapping_lists(input_list))
# 输出示例：[[0, 1, 2, 3], [4, 5, 7, 8, 6]]（元素顺序不影响结果）

补充说明 #

• 如果你希望合并后的子列表元素是有序的，只需要在返回结果时对每个分组排序，比如把最后一行改成：return [sorted(group) for group in groups.values()]
• 这个方法的时间效率很高，尤其是当嵌套列表里的元素数量很多时，路径压缩和合并优化能大大减少操作时间
• 即使子列表里只有单个元素，代码也能正确处理——如果这个元素没有和任何其他元素连通，就会单独成为一个子列表

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