如何借助关联ID列表高效重组Python字典列表？

你现有解法效率低的核心原因基本都是没有做id到对象的预映射，每次匹配id都全量遍历l1，时间复杂度随数据量增长呈平方级上升。

核心思路 #

• 首先对l1做一次单次遍历，构建以id为key、对应字典对象为value的哈希表，把单个id的查找耗时从O(n)降到O(1)
• 如果l2的子列表不存在id重叠、不需要处理跨组传递关联（和题目给出的示例场景一致），直接遍历l2的每个id组，从哈希表里取对应对象组装结果即可，整体是线性时间复杂度
• 如果存在id同时出现在多个l2子列表、需要合并传递关联的场景（比如[1,2]和[2,3]要合并为1、2、3同组），搭配并查集做连通分量合并即可，整体耗时依然接近线性

代码实现 #

适配题目示例场景（无跨组关联） #

def build_related_list(l1: list[dict], l2: list[list[int]]) -> list[list[dict]]:
    id_to_obj = {item["id"]: item for item in l1}
    result = []
    for id_group in l2:
        result.append([id_to_obj[obj_id] for obj_id in id_group])
    return result

拿题目给的样例输入跑这段代码，输出和预期结果完全一致。

适配传递关联场景（id可能跨子列表出现） #

如果业务里存在关联传递的情况，用下面的实现：

class DSU:
    def __init__(self):
        self.parent = dict()
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x: int, y: int) -> None:
        if x not in self.parent:
            self.parent[x] = x
        if y not in self.parent:
            self.parent[y] = y
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

def build_related_list(l1: list[dict], l2: list[list[int]]) -> list[list[dict]]:
    id_to_obj = {item["id"]: item for item in l1}
    dsu = DSU()
    # 合并所有关联关系
    for id_group in l2:
        if not id_group:
            continue
        first_id = id_group[0]
        for obj_id in id_group[1:]:
            dsu.union(first_id, obj_id)
    # 按连通分量分组
    group_collect = dict()
    for obj_id in id_to_obj:
        # 没出现在关联列表里的id会单独成组，不需要的话可以删掉这段判断
        if obj_id not in dsu.parent:
            group_collect[obj_id] = [id_to_obj[obj_id]]
            continue
        root = dsu.find(obj_id)
        if root not in group_collect:
            group_collect[root] = []
        group_collect[root].append(id_to_obj[obj_id])
    return list(group_collect.values())

效率说明 #

• 常规低效遍历实现的时间复杂度是O(len(l1) * l2总id数)，数据量到10万级就会有明显的秒级卡顿
• 上面给出的两种实现时间复杂度都是线性级O(len(l1) + l2总id数)，百万级数据量也能在毫秒级跑完，是该场景下的最优实现。

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