更新列表所有条目为所有相交条目并集的最快实现方法

你要实现的集合扩展本质是查找元素的连通分量，只要两个元素出现在同一个原始集合中就属于同一连通组，最终每个原始集合的扩展结果就是其包含元素所属连通组的全部元素。我们可以用并查集（DSU） 数据结构实现高效处理，时间复杂度接近线性，无需多次迭代即可一次得到正确结果。

实现思路 #

• 初始化并查集结构，用于维护元素的连通关系
• 遍历所有原始集合，将同一个集合内的所有元素合并到同一分组（取集合第一个元素作为锚点，其他元素都和锚点合并即可）
• 遍历完成后，汇总每个连通组的所有元素
• 遍历每个原始集合，取任意元素查找到对应连通组的所有元素，作为该集合的扩展结果

代码实现 #

class DSU:
    def __init__(self):
        self.parent = {}
    
    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):
        if x not in self.parent:
            self.parent[x] = x
        if y not in self.parent:
            self.parent[y] = y
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

def consolidate_list(arr):
    dsu = DSU()
    # 第一步：合并所有同集合内的元素
    for sublist in arr:
        if not sublist:
            continue
        # 取第一个元素作为锚点
        anchor = sublist[0]
        for num in sublist[1:]:
            dsu.union(anchor, num)
    # 第二步：汇总每个连通组的所有元素
    group = {}
    for num in dsu.parent:
        root = dsu.find(num)
        if root not in group:
            group[root] = []
        group[root].append(num)
    # 第三步：生成结果
    res = []
    for sublist in arr:
        if not sublist:
            res.append([])
            continue
        root = dsu.find(sublist[0])
        # 排序后返回，和示例结果顺序一致
        res.append(sorted(group[root]))
    return res

测试验证 #

用你给出的输入测试：

test_input = [
    [0, 5, 101],
    [8, 9, 19, 21],
    [78, 79],
    [5, 7, 63, 64]
]
print(consolidate_list(test_input))

输出结果完全符合预期：

[[0, 5, 7, 63, 64, 101], [8, 9, 19, 21], [78, 79], [0, 5, 7, 63, 64, 101]]

方案优势 #

• 时间复杂度接近O(Mα(N))，其中M是所有元素的总数量，α是阿克曼函数的反函数，增长极慢，实际运行接近线性时间，远优于两层循环的O(N²K)（K为平均集合大小）
• 无需多次迭代运行，一次处理即可得到最终结果
• 天然支持参差输入，对每个子列表的长度没有要求
• 不依赖numpy，纯Python实现，也可根据需要兼容numpy数组输入

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