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.
[3,2,1,5,6,4]and k = 2 Output: 5
[3,2,3,1,2,4,5,5,6]and k = 4 Output: 4
You may assume k is always valid, 1 ≤ k ≤ array’s length.
I have two solutions.
First one is simple, just two lines, first sort, then output the kth element.
Second is not hard too, first I build a max-heap, then output the kth element. (codes about max-heap see this)
Want to know more details of heap and heapsort, check my post:Heap and Heap-Sort algorithm.