Problem Description
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.
Implement KthLargest class:
- KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
- int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class KthLargest {
PriorityQueue<Integer> pq;
int size;
public KthLargest(int k, int[] nums) {
this.size=k;
pq = new PriorityQueue<>();
for(int i=0; i<nums.length; i++) pq.add(nums[i]);
while(pq.size() > k) pq.poll();
}
public int add(int val) {
pq.add(val);
if(pq.size() > size)
pq.poll();
return pq.peek();
}
}