Python二维列表重叠子列表合并去重功能实现求助

问题根因 #

你当前编写的代码仅会对比当前遍历的子列表和结果列表的最后一个分组，非相邻的重叠子列表无法被识别归类到同一分组，因此会输出错误结果。

实现方案 #

方案1：朴素迭代法（适合小数据量场景） #

遍历所有子列表，每个子列表和结果中已有的所有分组做重叠检查，只要和任意一个分组有公共元素就合并到该分组，没有重叠就新增分组。

def merge_overlap_sublists(input_list):
    result = []
    for sublist in input_list:
        current_set = set(sublist)
        # 存储需要合并的分组索引
        merge_indexes = []
        for idx, exist_set in enumerate(result):
            if not current_set.isdisjoint(exist_set):
                merge_indexes.append(idx)
        if not merge_indexes:
            # 没有重叠，新增分组
            result.append(current_set)
        else:
            # 合并所有关联分组 + 当前子列表
            merged = current_set
            for idx in reversed(merge_indexes):
                merged.update(result.pop(idx))
            result.append(merged)
    # 转换为排序后的列表格式返回
    return [sorted(list(s)) for s in result]

方案2：并查集实现（适合大数据量场景） #

把所有元素当做节点，同一个子列表内的元素属于同一连通分量，最后按连通分量分组排序即可，时间复杂度更低。

class UnionFind:
    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 merge_overlap_sublists(input_list):
    uf = UnionFind()
    for sublist in input_list:
        if not sublist:
            continue
        # 同一个子列表的元素全部连通
        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] = set()
        groups[root].add(num)
    # 排序后返回
    return [sorted(list(g)) for g in groups.values()]

测试验证 #

输入测试用例：

test_input = [[2,3],[1,2],[5,7],[5,8],[7,8,9],[1]]
print(merge_overlap_sublists(test_input))

输出结果：
[[1, 2, 3], [5, 7, 8, 9]]
和预期结果完全一致。

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