如何从索引对应的分类与成本列表中为每个分类选取最低成本值

实现逻辑 #

该问题核心是对每个分类取对应的最小成本后求和，最优时间复杂度为O(n)，仅需一次遍历即可完成，不需要额外排序操作：

• 初始化字典存储每个分类的当前最小成本
• 同步遍历分类列表和成本列表的每一组对应元素
• 若当前分类未在字典中记录，直接存入当前成本作为该分类的最小成本
• 若当前分类已存在记录，比较当前成本与已存储的最小成本，取更小值更新记录
• 遍历完成后，对字典中所有存储的最小成本求和即为最小总成本

代码示例（Python） #

def calc_min_total_cost(category_list, cost_list):
    min_cost_map = {}
    # 同步遍历两个列表的对应元素
    for cate, cost in zip(category_list, cost_list):
        # 仅当分类未记录，或当前成本比已记录值更小时更新
        if cate not in min_cost_map or cost < min_cost_map[cate]:
            min_cost_map[cate] = cost
    # 所有分类最小成本求和
    return sum(min_cost_map.values())

# 测试用例
category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]
print(calc_min_total_cost(category_list, cost_list))
# 输出结果：57

效率说明 #

• 时间复杂度O(n)：仅需遍历一次长度为n的列表，字典的查询、插入操作平均时间复杂度均为O(1)
• 空间复杂度O(k)：k为不同分类的总数量，通常远小于列表长度n
• 若你的分类为连续非负整数，可替换为数组存储最小成本，读写性能会略高于字典；字典实现通用性更强，支持任意可哈希的分类类型（如字符串、元组等）

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