Python查找字典中跨键覆盖度最高的Top N值实现方案

需求描述 #

• 输入为多值映射结构：每个键对应多个值，单个值在任意键下仅出现一次
• 需选出覆盖键范围最广的前5个值，不按值的总出现频次排序，核心排序规则是优先选择能覆盖最多「未被已选值覆盖的键」的值
• 规则示例：

若值"abc"覆盖100个键中的51个，值"def"共覆盖49个键但其中48个已经被"abc"覆盖，仅覆盖10个全新未覆盖键的"ghi"优先级高于"def"，应优先入选。

现有代码问题 #

已编写的文件读取代码如下，存在未拆分同键下多值的逻辑缺陷：

with open("all.txt", "r") as f:
    lines = f.readlines()

dict1 = dict()

for line in lines:
    line = line.replace("\n", "")
    linesplit = line.split(":")
    if linesplit[1] in dict1:
        dict1[linesplit[1]].append(linesplit[0])
    else:
        dict1[linesplit[1]] = [linesplit[0]]

示例验证 #

参考输入数据：

dog:1,3
cat:2,5
snake:2,4
monkey:3,1
rabbit:3,1

数据逻辑说明：

• 值1和值3覆盖的键完全重合（dog、monkey、rabbit），共3个键
• 值2覆盖2个未被值1覆盖的键（cat、snake）
• 其余值覆盖的键均存在重合，新增覆盖数更低
  因此前2位结果应为：

1
2

实现方案 #

该需求是典型的贪心求解集合覆盖问题，执行逻辑如下：

• 修正文件读取逻辑，拆分每行冒号后逗号分隔的多个值，构建「值 -> 对应键集合」的映射
• 维护全局已覆盖键集合，初始为空
• 循环执行选值逻辑，直到选满5个值或无新键可覆盖：
  • 遍历所有未入选的值，计算当前值能新增覆盖的键数（即该值对应键集合与全局已覆盖集合的差集大小）
  • 选出新增覆盖数最大的值，加入结果列表
  • 将该值对应的所有键加入全局已覆盖集合

完整代码 #

# 读取文件构建值到键集合的映射
value_to_keys = dict()

with open("all.txt", "r") as f:
    for line in f:
        line = line.strip()
        if not line:
            continue
        key, values_str = line.split(":", 1)
        # 拆分同键下的多个值
        for v in values_str.split(","):
            v = v.strip()
            if v not in value_to_keys:
                value_to_keys[v] = set()
            value_to_keys[v].add(key)

selected_values = []
covered_keys = set()
# 选前5个值
for _ in range(5):
    best_value = None
    max_new_cover = -1
    # 遍历所有未选值找新增覆盖最多的
    for v, keys in value_to_keys.items():
        if v in selected_values:
            continue
        new_cover = len(keys - covered_keys)
        if new_cover > max_new_cover:
            max_new_cover = new_cover
            best_value = v
    # 没有新键可覆盖时提前终止
    if max_new_cover <= 0:
        break
    selected_values.append(best_value)
    covered_keys.update(value_to_keys[best_value])

# 输出结果
for res in selected_values:
    print(res)

代码运行在示例数据上时，会按预期输出1和2，符合需求。

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