转载

LeetCode 第703题 Kth Largest Element in a Stream 【堆】Java

原题地址： https://leetcode.com/problems/kth-largest-element-in-a-stream/

设计一个类寻找一个数据流里面的第 k 大的元素。注意是指排序后的第k大元素，而不是第k个不重复元素。

你的 KthLargest 类应该有一个构建器接受一个整数 k 和一个整数数组 nums ，包含流的初始元素。每次调用方法 KthLargest.add ，返回流里面的第 k 大的元素。

例子:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

注意:

你可以假定 nums 的长度 ≥ k-1 而且 k ≥ 1 。

解决方案1：一个最大堆加一个最小堆

这类题目肯定可以想到堆，但是做起来稍微有点麻烦。我们思考这个题，会发现，首先我们一开始可以构建一个最大堆，这样我们就得到最初始的的最大k个元素。

然后如果add的新的数字小于当前的第k个最大元素，那么这个add操作对结果毫无影响，第k个最大元素没变。如果，add的新数字比当前的第k个最大元素大，我们就会发现它会被当前的第k个最大元素挤走。

所以，我们可以用一个最小堆来保存k个最大的元素。如果新加的数字小于等于最小堆的最小元素，则不做任何修改，输出最小堆的最小元素即可。

如果新加的元素比较大，我们就用它替换堆的第一个元素（堆顶，即最小值），然后minHeapify(1)，这样最小堆就可以又保证最小值在堆顶了。

所以构建器的代码如下：

LeetCode 第703题 Kth Largest Element in a Stream 【堆】Java

add方法代码：

这个实现里用的是我们之前提到的最大堆最小堆的标准实现，只是给最小堆类加了一个方法replaceTop：

最后耗时为60毫秒，好于66.06%的Java代码。

解决方案2：一个最小堆

仔细思考方案1后我们发现，最大堆是多余的。一个最小堆也可以解决问题。首先我们把一个k大小的数组全部成员初始化为Integer.MIN_VALUE。然后把它构建成一个最小堆，然后用我们之前实现的add方法加入全部元素，我们会发现堆里面就是最大的k个元素。然后继续用add动态加入新的数字，也不会影响这一特性。其实复杂度差异不大，但是代码就简单多了。add和replaceTop都不用修改，只需要实现一个新的构造器即可。

代码地址： https://github.com/tinyfool/leetcode/tree/master/src/p0703

也请参阅《 Leetcode专题堆结构和堆排序》，文章介绍了堆和堆排序，以及最大堆的实现。

原文 http://codechina.org/2019/07/leetcode-703-kth-largest-element-in-a-stream-java/

正文到此结束

所属分类：编程技术 Java

本文标签： 数据文章 UI ACE http https src git value java 代码 2019 GitHub stream API Master
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二