Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
KthLargest class will have a constructor which accepts an integer
k and an integer array
nums, which contains initial elements from the stream. For each call to the method
KthLargest.add, return the element representing the kth largest element in the stream.
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
You may assume that
nums‘ length ≥
k ≥ 1.
Solution 1: A max-heap and a min-heap
Try to solve this kind of problem, you can easily think about the heap, but this problem is a little complex. First I build a max-heap, so I can get the initial kth largest element.
Then when we add a number small or equal than the current kth largest element, it will cause nothing, we can just ignore it. When it is larger than the current kth largest element, the original kth largest element need be removed, and the new number should add to the top-k numbers to compare which is the smallest.
So we can use a min-heap save the top-k numbers. If the new number is smaller, don’t touch min-heap, just output the top of the heap.
If the new number is larger, we use it to replace the top of the heap, and minHeapify(1), then we can ensure the top of the heap is the kth largest element, so then we output it.
So the code of the constructor like this:
And we add a method replaceTop to min-heap:
Runtime: 61 ms, faster than 66.06% of Java online submissions for Kth Largest Element in a Stream.
Memory Usage: 48.1 MB, less than 42.98% of Java online submissions for Kth Largest Element in a Stream.
Solution 2: One min-heap
After thinking about solution1, we found the max-heap is not necessary. One min-heap can solve this problem too. First, we create an array size is k, make every element in this array is Integer.MIN_VALUE. Then we make it a min-heap, use the add method to add all elements in. We will find out this heap is the top-k elements already. And add more numbers will not change this property. The time complexity is not much different from solution 1. But the code is simpler and easier. We don’t need to change the add and the replaceTop method, we only need a new constructor.
Want to know more details of heap and heapsort, check my post:Heap and Heap-Sort algorithm.