如何合并存在公共元素的嵌套列表,公共元素本身为列表或元组
错误原因分析
你原有代码报错的核心原因有两个:
- 列表是不可哈希类型,不能直接作为
set的元素或者字典的key,subl = list(set(subl))这一步本身就会直接报错,只是你可能先触发了后面的报错。 sublswitch的键是range生成的整数,你在循环里对整数类型调用.values()方法,自然会触发AttributeError: 'int' object has no attribute 'values'的报错。
正确实现方案
这个需求本质是连通分量合并问题:只要两个子列表存在公共元素,就归为同一组,最终每组保留所有出现过的唯一元素即可。
实现代码如下:
def merge_sublists(data): # 先把不可哈希的列表转成元组方便做交集判断 processed = [] for sub_list in data: processed.append(set(tuple(item) for item in sub_list)) groups = [] for current in processed: merged = False # 遍历已有的分组,看是否有交集 for i in range(len(groups)): if current & groups[i]: # 有交集就合并 groups[i] |= current merged = True break if not merged: # 没有交集就新增分组 groups.append(current) # 把元组转回列表,按示例顺序排序输出 result = [] for group in groups: sorted_group = sorted(list(item) for item in group) result.append(sorted_group) return result # 测试示例数据 data = [ [[0,1],[2,3],[4,5]], [[2,3],[4,5]], [[4,5]], [[6,7],[8,9],[10,11]], [[8,9],[10,11]], [[10,11]], [[12,13],[14,15],[16,17],[18,19],[20,21]], [[14,15],[16,17],[18,19],[20,21]], [[16,17],[18,19],[20,21]], [[18,19],[20,21]], [[20,21]] ] merged = merge_sublists(data) print(merged)
运行后输出和你要求的结果完全一致:
[[[0, 1], [2, 3], [4, 5]], [[6, 7], [8, 9], [10, 11]], [[12, 13], [14, 15], [16, 17], [18, 19], [20, 21]]]
如果处理的数据量很大,可以替换为并查集实现进一步降低时间复杂度,上述方案对于中小规模数据已经足够简单高效。
内容的提问来源于stack exchange,提问作者Fonnie
相关产品推荐
相关产品推荐

