基于共享元素的列表聚类：寻求更高效实现方案

你的需求本质是找出列表中所有连通元素组——只要两个元素出现在同一个子列表里，就属于同一连通组，最终要把每个连通组的元素合并成一个子列表。原方案的循环迭代聚类方式虽然能解决问题，但每次循环都要重新遍历所有元素、构建映射，当数据规模较大时，冗余计算会导致时间效率明显下降。

最优方案：并查集（Union-Find/DSU） #

并查集是专门处理动态连通性问题的数据结构，时间复杂度接近线性（实际是O(α(N))，α是阿克曼函数的反函数，增长极慢，几乎可视为常数），完美契合你“时间效率优先”的需求。

实现代码 #

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    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):
        # 按秩合并优化：把秩小的树合并到秩大的树上，保持树的平衡
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

def group_lists(list_of_lists):
    uf = UnionFind()
    
    # 初始化所有元素的父节点和秩
    for sublist in list_of_lists:
        for num in sublist:
            if num not in uf.parent:
                uf.parent[num] = num
                uf.rank[num] = 0
        # 将当前子列表中的所有元素连通
        if len(sublist) >= 2:
            first = sublist[0]
            for num in sublist[1:]:
                uf.union(first, num)
    
    # 构建根节点到元素组的映射
    groups = {}
    for num in uf.parent:
        root = uf.find(num)
        if root not in groups:
            groups[root] = []
        groups[root].append(num)
    
    # 转换为最终的列表格式（如需保留顺序可去掉sorted，按需调整）
    return [sorted(group) for group in groups.values()]

# 测试示例
o = [[1,2],[3,4],[2,3],[5,4]]
print(group_lists(o))  # 输出: [[1, 2, 3, 4, 5]]

方案优势说明 #

• 时间效率拉满：只需要两次遍历（一次初始化+连通元素，一次分组），没有循环迭代的冗余计算，处理大规模数据时优势极其明显。
• 代码简洁易维护：并查集的核心逻辑清晰，可读性强，后续调整需求（比如不需要排序、需要保留元素出现顺序）也很方便。
• 空间可控：只需要存储元素的父节点和秩信息，空间开销远低于多次循环的原方案。

对比原方案的核心提升 #

原方案每次循环都要重新构建元素到子列表的映射，再合并子列表，时间复杂度会随着聚类轮次增加而上升；而并查集方案只需要线性时间就能完成所有连通操作，是当前场景下的最优解。

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