如何为每个类别选择最低成本值？

Question

我有两个元素数量相同的列表。在第一个列表中，一个元素代表一个类别类型。在第二个列表中，一个元素代表一种成本。指数一一对应

例如：

category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]

在每个品类都挑一个的条件下，我想把成本降到最低。我该如何实施？更快，更好。感谢您的帮助。

Answer 1

您可以将每个类别的最低成本存储在 dict 中。

category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]

min_cst = dict()
for cat, cst in zip(category_list, cost_list):
    if cat in min_cst:
        min_cst[cat] = min(min_cst[cat], cst)
    else:
        min_cst[cat] = cst

print(min_cst)
# {1: 22, 2: 11, 3: 11, 4: 13}

时间复杂度O(N)，space复杂度O(N)。

Answer 2

解决方案 1:

您可以迭代 category_list 并在关键字为 category_list 的字典中保存 cost_list 的最小值，您可以使用 dictionary.get() 并将最小值替换为最小值以前存在于字典中。

category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]

dct_min = {}
for idx in range(len(category_list)):
    min_item = dct_min.get(category_list[idx], cost_list[idx])
    # alternative solution by thanks @Stef
    # min_item = dct_min.setdefault(category_list[idx], cost_list[idx]); if cost_list[idx] < min_item: ...
    if cost_list[idx] <= min_item:
        dct_min[category_list[idx]] = cost_list[idx]
print(dct_min)

输出：

{1: 22, 2: 11, 3: 11, 4: 13}

解决方案 2：（您可以使用 zip 然后排序 tuple 第一个碱基 index0 然后 index1 并将排序的 tuple 转换为 dictionary 我们知道在 dictionary 中我们只有一个 key.)

zip_lsts = list(zip(category_list, cost_list))
dict(sorted(zip_lsts, key=lambda element: (element[0], element[1]),reverse=True))
# {4: 13, 3: 11, 2: 11, 1: 22}

Answer 3

我推荐了这段代码。在这里我们使用 python 中的预构建方法 'zip' 来迭代获取 category_list 和 cost_list 所以我认为这是很好的做法然后我使用条件表达式来创建我的逻辑.首先，我想确定该类别中已经在我的 x_dict 中的那个表达式是否为真我使用 'min' 预构建方法来比较已经存在的值和相关键的新值。所以它有助于管理我们的逻辑。否则，该键不存在，那么我们可以第一次添加键值对。字典键必须是唯一的，这就是我们使用此逻辑的原因。

category_list = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]
x_dict=dict()
for cat,cost in zip(category_list,cost_list):
    if cat in x_dict:
        x_dict[cat]=min(x_dict[cat],cost)
    else:
        x_dict[cat]=cost


print(x_dict)

输出

{1: 22, 2: 11, 3: 11, 4: 13}

我们可以直接使用zip方式，转成字典。它可以过滤唯一键，但情况是它给出了我们使用的相关键的最后一个值，如下所示。

x=dict(zip(category_list,cost_list))
print(x)

输出

{1: 22, 2: 11, 3: 12, 4: 13}

您可以看到给定列表的最后成本分配给相关类别。这就是我们为代码提供的逻辑。

Answer 4

由于已经有三个使用 dict 的几乎相同的答案，这里是每个类别仅使用一次 min 的不同答案：

category_list  = [1, 2, 2, 1, 3, 3, 3, 3, 4, 2]
cost_list      = [30, 45, 21, 22, 21, 32, 11, 12, 13, 11]

pick_indices   = [min((i for i in range(len(cost_list)) if category_list[i] == cat), key=lambda i: cost_list[i]) for cat in set(category_list)]
pick_totalcost = sum(cost_list[i] for i in pick_indices)

或者：

pick_costs     = [min(cost for i,(cost,cat) in enumerate(zip(cost_list, category_list)) if cat == c) for c in set(category_list)]
pick_totalcost = sum(pick_costs)

如何为每个类别选择最低成本值？

How do I pick the lowest cost value for each category?

python

algorithm

data-structures