We’re preparing your current view and syncing the latest data.
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) average time complexity.
An integer array nums and an integer k.
The kth largest element in the array as an integer.
1 <= k <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4
Example 1
Input
nums = [3,2,1,5,6,4], k = 2
Output
5
Explanation
The second largest element is 5.
Example 2
Input
nums = [3,2,3,1,2,4,5,5,6], k = 4
Output
4
Explanation
The fourth largest element is 4.