相关疑难解决方法(0)

在算法中,每当我添加一个值时,我都必须计算数据集的第75个百分位数.现在我这样做:

1. 获得价值 x
2. x在后面插入已排序的数组
3. 交换x,直到数组排序
4. 读取位置处的元素 array[array.size * 3/4]

点3是O(n),其余是O(1),但这仍然很慢,特别是如果阵列变大.有没有办法优化这个？

UPDATE

谢谢尼基塔!由于我使用的是C++,因此这是最容易实现的解决方案.这是代码:

template<class T>
class IterativePercentile {
public:
  /// Percentile has to be in range [0, 1(
  IterativePercentile(double percentile)
    : _percentile(percentile)
  { }

  // Adds a number in O(log(n))
  void add(const T& x) {
    if (_lower.empty() || x <= _lower.front()) {
      _lower.push_back(x);
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
    } else {
      _upper.push_back(x);
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
    }

    unsigned size_lower = (unsigned)((_lower.size() + _upper.size()) * _percentile) + 1;
    if (_lower.size() …

假设我有一些类型的集合,例如

IEnumerable<double> values;

现在我需要从该集合中提取k个最高值,对于某些参数k.这是一种非常简单的方法:

values.OrderByDescending(x => x).Take(k)

但是,这(如果我理解正确的话)首先对整个列表进行排序,然后选择前k个元素.但是如果列表非常大,并且k相对较小(小于log n),则效率不高 - 列表以O(n*log n)排序,但我想从列表中选择k个最高值应该更像O(n*k).

那么,有没有人建议更好,更有效的方法来做到这一点？