This question is part of NeetCode150 series.
Problem Description
Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element. You must solve it in O(n) time complexity. leetcode
Solution
The trivial way is to sort the list and return the element at K-1 index.
We can also make use of Max Heap which is going to O(N + KlogN) time complexity.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
for(int i=0; i<nums.length; i++){
pq.add(nums[i]);
}
int ans = 0;
for(int i=1; i<k; i++){
pq.poll();
}
return pq.poll();
}
}