Description
https://leetcode.com/problems/kth-largest-element-in-an-array/
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
Explanation
Use heap is easy to find k largest.
Python Solution
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return heapq.nlargest(k, nums)[-1]- Time complexity: O(N log(k)).
- Space complexity: O(k).
/** java **/
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue q = new PriorityQueue();
for(int i: nums){
q.offer(i);
if(q.size() > k) {
q.poll();
}
}
return q.peek();
}
// Another approach
public int findKthLargest1(int[] nums, int k) {
if(nums == null || nums.length == 0 ) return -1;
int len = nums.length;
Arrays.sort(nums);
return nums[len-k];
}
}