python - 以相同的方式、算法或数学方程从列表中获取元素

Question

我有一个元素列表，例如:[1, 10, 10]，它代表我拥有的每种类型的产品数量。 用户想要购买每种类型的 10 产品，且数量相同。 因此结果列表将为 [1, 5, 4] 或 [1, 4, 5]。 我通过 while 和 for 循环完成了此操作，迭代列表中的所有元素，如果没有达到最大数量，则增加计数器，直到获得 10 个产品，或者所有库存都为空。

但是在数据非常大的情况下，我遇到了一些性能问题，并且我需要在多个位置应用它。

我的问题是，我是否可以用数学方程或更好的算法来做到这一点。 对于数学方程，我提取了要求解的数据，但我有太多未知变量:

21/x = a
21/y = b
21/z = c
a + b + c = 10

其中21是所有产品的总和，10是用户需要的产品数量。

Answer 1

O(n) 解决方案(具有 O(n log(n)) 排序):

amounts = [1, 10, 10]
left_to_buy = 12

sorted_amounts = list(sorted([amount, index] for index, amount in enumerate(amounts)))

for idx, (amount, _) in enumerate(sorted_amounts):
    buy = min(left_to_buy//(len(amounts)-idx), amount)
    sorted_amounts[idx][0] -= buy
    left_to_buy -= buy

final_amounts = [a for a, i in sorted(sorted_amounts, key = lambda t: t[1])]
bought = [amount - final_amounts[i] for i, amount in enumerate(amounts)]

print(final_amounts, bought)
#[0, 5, 4] [1, 5, 6]

我们首先对可用项目的列表进行排序(我们将它们的索引保存在一个元组中，以便在最后将列表恢复到原始顺序)。

然后，我们从每件商品中删除剩余要购买的部分，如果没有足够的，则删除全部。

最后，我们将列表按原来的顺序放回

编辑:我错过了您的列表已经排序的事实...在这种情况下，它会变得更短:

amounts = [1, 10, 10]
left_to_buy = 12

res = [] 

for idx, amount in enumerate(amounts): 
    buy = min(left_to_buy//(len(amounts)-idx), amount) 
    left_to_buy -= buy 
    res.append(buy) 

print(res) 
# [1, 5, 6]