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.
Example 1:
Input ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8] Explanation KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
Constraints:
1 <= k <= 1040 <= nums.length <= 104-104 <= nums[i] <= 104-104 <= val <= 104104 calls will be made to add.k elements in the array when you search for the kth element.class KthLargest {
int k;
List<Integer> nums;
public KthLargest(int k, int[] nums) {
this.k = k;
this.nums = Arrays.stream(nums).boxed().sorted().collect(Collectors.toList());
}
public int add(int val) {
int idx = 0;
nums.add(binarySearch(val), val);
// System.out.println(nums);
return nums.get(nums.size() - k);
}
private int binarySearch(int val) {
int lt = 0, rt = nums.size() - 1;
while (lt <= rt) {
int mid = lt + (rt - lt / 2);
if (nums.get(mid) < val)
lt = mid + 1;
else
rt = mid - 1;
}
return lt;
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/class KthLargest {
int k;
List<Integer> nums;
public KthLargest(int k, int[] nums) {
this.k = k;
this.nums = Arrays.stream(nums).boxed().sorted().collect(Collectors.toList());
}
public int add(int val) {
int idx = 0;
while(idx<nums.size() && nums.get(idx)<val)
idx++;
nums.add(idx, val);
// System.out.println(nums);
return nums.get(nums.size() - k);
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/class KthLargest {
int k;
Queue<Integer> stream; // minHeap Impl
public KthLargest(int k, int[] nums) {
this.k = k;
stream = new PriorityQueue<>();
for (int i : nums)
stream.offer(i);
while (stream.size() > k)
stream.poll();
}
public int add(int val) {
if (stream.size() < k || stream.peek() < val) {
stream.offer(val);
while (stream.size() > k)
stream.poll();
}
return stream.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/