Kth Largest Element in an Array
Return the k-th largest element in the array.
Examples
Input: [[3,2,1,5,6,4],2]
Output: 5
Input: [[3,2,3,1,2,4,5,5,6],4]
Output: 4
Hints
Consider using a max-heap to store all elements, then extract the k-th largest element by performing k extractions.
Implement the QuickSelect algorithm to find the k-th largest element in average O(n) time, with a worst-case of O(n^2) if pivot selection is naive.
Optimize QuickSelect by using the "median of medians" algorithm to select a good pivot, ensuring a worst-case time complexity of O(n).
Related Problems
Kth Largest Element in an Array
Return the k-th largest element in the array.