python:算法——从均值中收集项目

Question

不确定这是否是正确的地方，但我有一个与算法相关的问题，我想不出一个有效的算法。所以想分享我的问题陈述.. :)为了简化我要解释的内容，让我创建一个假设示例。

假设，我有一个列表，其中包含一个包含两件事的对象..

lets say product id and price

现在，这是一个很长的 list ..有点像 list ..出于这个我已经定义了三个价格段.. lowprice, midprice and highprice然后是 k1、k2、k3，其中 k1、k2 和 k3 是比率。所以，现在的工作是，我必须从这个庞大的库存中收集产品，这样就有 n1 个产品来自低价范围，n2 个产品来自中等价格范围，n3 个产品来自高价范围......其中 n1:n2: n3 == k1:k2:k3

现在，我如何有效地实现以下目标。我的目标是低价位是 100 美元我必须从这个系列中收集 20 种产品..中间价位大概是 500 美元等等

所以我从 100 美元开始......然后寻找 90 到 100 之间以及 100 到 110 之间的项目假设我在间隔 1 低 (90,100) 中找到了 5 个产品，在间隔 1 高 (100,110) 中找到了 2 个产品然后，我进入下一个低区间和下一个高区间。我一直这样做，直到我得到这个区间内的产品数量。

我该怎么做？也可能有这样的情况，当特定价格范围内的产品数量少于我需要的数量时……(也许中间价格范围是 105 美元……)。那么在这种情况下我应该怎么做……请原谅我，如果这不是正确的平台.. 从问题中你可以看出这更像是一个有争议的问题，而不是“我收到这个错误”类型的问题。谢谢

Answer 1

您可能正在寻找 selection algorithm .
首先找到n1第 ' 个最小的元素，让它成为 e1 ，下限列表是满足element <= e1的所有元素.
对其他范围执行相同的操作。

下界列表的伪代码:

getLowerRange(list,n):
  e <- select(list,n) 
  result <- []
  for each element in list:
     if element <= e:
         result.append(element)
  return result

请注意，如果有许多“相同”的项目[结果将是一个更大的列表]，此解决方案将失败，但找到这些项目并将其从结果列表中删除并不难。

注意选择算法是O(n) ，因此该算法将消耗与列表大小相关的线性时间。