Python 海量嵌套整数列表查找合并操作的优化方案咨询

原有实现性能瓶颈 #

你当前的双层循环实现时间复杂度为O(NMK)，其中N是遍历的查询元素总数、M是子列表总数量、K是子列表平均长度。重复遍历全量子列表、列表in操作的线性复杂度、后续单独扁平化去重是主要性能损耗点。另外原有实现按range(len(list_ref))生成查询范围，会漏掉值大于子列表总数的元素的结果（比如示例中的100、42）。

最优优化思路：反向映射单次遍历 #

仅需遍历一次所有子列表，构建「元素 -> 所有包含该元素的子列表的去重元素集合」的映射，时间复杂度直接降到O(MK)*，是该场景下的理论最优复杂度。

实现代码 #

from collections import defaultdict

# list_ref 为你的原始嵌套列表
elem_map = defaultdict(set)

# 单次遍历所有子列表
for sublist in list_ref:
    sub_elem_set = set(sublist)
    # 当前子列表的所有元素，都需要关联当前子列表的全部元素
    for elem in sub_elem_set:
        elem_map[elem].update(sub_elem_set)

# 如果需要生成从0开始连续索引的结果列表
max_elem = max(elem_map.keys()) if elem_map else 0
gr_cl_set = [list(elem_map.get(i, set())) for i in range(max_elem + 1)]

# 如果元素稀疏不需要连续索引，直接用elem_map查询即可，节省内存
# 比如查包含0的所有子列表的去重元素：list(elem_map.get(0, set()))

优化优势 #

• 无重复遍历子列表的开销，仅需一次全量扫描
• 集合存储自动去重，省略单独的扁平化、转set步骤
• 集合的插入、查询都是O(1)复杂度，远快于列表的线性操作
• 自动覆盖所有出现过的元素，不会遗漏大值元素的结果
• 稀疏元素场景下用字典存储结果，可避免大量空列表占用内存

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