相关疑难解决方法(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() …