Given an integer array nums and an integer k, return the kth largest element in the array.
This means the kth largest in sorted order, not the kth largest distinct value. Can you do better than sorting everything?
Examples
Example 1
- Input
- nums = [3, 2, 1, 5, 6, 4], k = 2
- Output
- 5
Example 2
- Input
- nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
- Output
- 4
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4