首页 » 算法 » 正文

算法:求一个源源不断到来数据中的前K个最大(小)元素?以及第K个最大(小)元素?

问题描述:

假如现在给你一个无序的一连串整数,元素个数不确定,数据量很大,甚至源源不断地到来,但是你需要知道到目前为止的前K个最大(小)元素,以及第K个最大(小)元素。

算法实现:

因为“求前K个最大元素”和“求前K个最小元素”这两个问题的实现思路是一致的,因此下面以“求前K个最大元素”举例分析。

方案一:如果数据量不是很大,可以将所有数据放在数组中排序,然后返回前K个最大元素即可。

方案二:很明显,方案一在数据量特别大时效率会非常低,而且如果数据量不确定且源源不断地到来呢?因此我们可以换一种思路,维护一个固定长度为 K 的数组,然后每次新元素到来时将之插入到合适位置并踢出此时数组中的最小元素。这样数组中维护的永远都是前K个最大元素,而且不管数据量有多大,只要每次把数组中最小元素剔除出去即可。

方案三:进一步思考,我们可以发现方案二也有一个明显缺点,那就是每次都需要查找当前数组中的最小值,而且还要把新值插入到数组中的合适位置(如果新值比最小值大),而这个开销也是比较大的。那么我们有没有办法降低这个开销呢?答案肯定是可以的,那就是使用 最小堆 这种数据结构(PS:而且堆这种数据结构在存储形式上表现为数组结构,存储成本很低)。由最小堆的定义可知它的第一个元素(根节点)永远是堆中最小值,这样我们就可以很方便地将新值和这个最小值比较,如果新值小于堆中根节点,那么不需要调整,相反则需要进行向下调整,调整的效率为O(log2 K),这样一来总体效率就变成了O(N * log2 K)。可见,这种方案效率很高,而且存储成本也很低,因此我将在下面给出使用该方案实现的示例代码,以供大家参考。

示例代码输出如下:

需要注意的是,上面的示例代码使用了我自己实现的优先队列(PS:优先队列的本质就是最大堆/最小堆),如需参考该类的实现可以看我的这个项目:https://gitee.com/zifangsky/DataStructure。当然,大家也可以直接使用JDK中的优先队列(java.util.PriorityQueue)。

发表评论

*