Aja*_*aur 7 arrays algorithm stream data-structures
我有一个正在运行的整数流,如何在任何时间点从该流中获取最大的k个元素.
ami*_*mit 16
最简单的解决办法是将填充最小堆大小k.
首先,使用第一个k元素填充堆.
接下来,对于流中的每个元素 - 检查它是否大于堆的头部,如果是 - 弹出当前头部,然后插入新元素.
在流中的任何时刻 - 堆都包含最大的k元素.
该算法是O(nlogk),n到目前为止在流中遇到的元素数量.
另一种解决方案,在某些情况下,在渐近复杂性方面稍微复杂但理论上更好,是保持2k元素数组.
首先,加载前2k个元素.
运行选择算法,找到最高的算法k.丢弃其余的,此时你只剩k下数组中的元素.
现在,再次使用下一个k元素填充数组,然后重复.
在每个点,数组包含k最大的元素,以及最多k不是最大的元素.您可以为此阵列上的每个查询运行选择算法.
运行时分析:
维护阵列:每个选择算法都是O(2k) = O(k).每个k元素都会执行一次,因此n/k,如果n指示到目前为止看到的元素数量,则会给出我们O(n/k * 2k) = O(n).
另外,每个查询是O(k),如果查询的数量是Q,这给我们O(n + Q*k)运行时.
为了使这个解决方案更有效,我们需要 Q*k < nlogk
Q*k < nlogk
Q < n/k * logk
因此,如果如上所述限制查询的数量,则该解决方案在渐近复杂度方面可能更有效.
实际上,通常使用min-heap解决方案来获得top k,至少在我看到它需要的时候.