215 - Kth largest element in an array
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.
There are several solutions for this problem.
- Arrays.sort time complexity is O(NlogN)
- max-heap time complexity is O(N + KlogN)
- min-heap First put k elements into heap, compare elements after A[k - 1] with root elements in the heap. if A[i] is larger than root, pop root and insert A[i]. Time complexity is O(K + (N - K)logK)
- Quick select In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.
- Randomized Quick Select This optimizes the worst case to O(n)
- Optimal