1

我有一个流（我不知道它的长度，理论上可能是无穷大）。

我一一阅读流的元素。

每次从流中读取一个元素时，我都希望能够返回k迄今为止读取的最大元素。

（理想情况下，对我来说，这将是 python 和/或 lisp/scheme 中的代码）。

K 在开始时读取，K 可以是 NUMBER（第 3、4 个），也可以是 PROCENT（到目前为止读取的元素总数的 K %）。如果K=1/2，表示每次都提取中值元素……比如读取第N个元素后，必须返回第N/2个最大元素

示例 K=1/2：

3 -> 3
3,4 -> 3
3,4,2 -> 3
3,4,2,1 -> 2
etc.

我认为这个例子足以澄清这个问题。我需要尽可能少的时间来提取第 K 个元素。（这假设在 O(1) 中读取流，然后插入读取的值，然后提取第 K 个元素）。

我想要任何比 O(n) 更好的解决方案。

4

4 回答 4

1

我会使用一个包含第 k 个最大元素的堆（或者在百分比的情况下使用包含所有元素的二叉搜索树）。这给了你 O(Log(k)) （或 O(Log(n)) 在百分比的情况下）。

第k个案例：

  • 如果新元素小于堆的最小值，则第 k 个最大的是堆的最小值。
  • 否则用新元素替换堆的最小值并堆化，第k个最大的是堆的新最小值。

案例百分比：在二叉搜索树中插入新元素，在这样的树中，很容易找到第k个元素。

于 2012-07-30T23:20:18.120 回答
1

因此，由于您需要第 k 个元素并且在运行算法之前已知 k，因此首先观察您需要存储最多 k 个元素，k 个最小元素。当您阅读新元素时，您需要在某些数据结构中插入元素，以保持其属性并有机会快速检索答案。1）您可以使用最多具有 k 个元素的最大堆。将元素插入到堆中（log（k）），然后如果您有超过 k 个元素（准确地说是 k+1），您需要 extract_max O(log(k)) 来提取和重建，答案将在堆顶访问 O(1)。因此，每次需要 log(k) 来获得第 k 个元素，所有元素的总数 - n * log(k)。

2）如果使用百分比，元素的位置将根据处理的元素数量动态计算，这里您可以使用订单统计树，http ://en.wikipedia.org/wiki/Order_statistic_tree具有相同的日志（数量元素）插入和日志（元素数量）查找。

于 2012-07-31T02:14:11.717 回答
0

如果您保留到目前为止看到的k个最大元素的排序列表，则始终可以返回列表中的最小元素。插入列表是O(k)并且得到最小的是O(1)。由于列表的大小不取决于n ，因此它在n方面是恒定的。

编辑 2：正如我在下面的评论中所说，我认为跳过列表可能是该列表的最佳选择。如果我没记错的话，它的插入时间为O(log k)，删除最小元素的时间为O(1) ，空间为 O (k log k)（相对于链表的O(k) ）。

于 2012-07-30T22:07:45.913 回答
0

堆是体面的。O(1) 查找最小值，O(logn) 删除。

对于这类问题，平均而言，Treap 非常快（很好的常数）。它们允许在 O(logn) 时间内访问（或删除）最小或最大值。 http://stromberg.dnsalias.org/~strombrg/treap/ 那里有一个“巢”模块（最好），就是为了这种事情。

红黑树的速度并不快，但它们的性能成本分布相当平稳，因此您不会像使用 treap 那样获得快-快-快-慢-快-快-快-慢。相反，它更像是中等-中等-中等-中等。

在这里尝试“手指树”可能会很有趣。据称，手指树给出了 O(1) 查找树中最小和最大值的方法。我不确定删除。

于 2012-07-30T23:40:55.787 回答