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.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
Analysis
It’s easy to first sort the array, then pick up the Kth largest element. The time complexity is O(nlogn) if we use quick sort.
Min Heap Based Method
A better method is use a min heap or PriorityQueue with size K.
[Read More...]