Background knowledge
The formula relation of Kth big and its element position (0-indexed array)
0, 3, 6, 7, 8
5 elements
1st big is pos 4 = 5 - 1
2nd big is pos 3 = 5 - 2
K big is pos [length - K]
Idea of solution
How to find Kth-largest in O(N) time complexity?
- quickSort = (list, pivot) =>
quickSort(list.filter(smaller than pivot))::
pivot::
quickSort(list.filter(greater than pivot)) - Let's say this is 0-indexed array, after 1st round of quickSort, say pivot is at index
p - we know that
palready stays at the correct position by when the array is fully sorted - for this is a 0-indexed array, array[p] is the [array.lenth - p]th big one
- if [array.length - p] is K, we already have the answer
- if [array.length - p] < K, we know that Kth-largest falls in right segment, recursively quickSort right segment
- if [array.length - p] > K, we know that Kth-largest falls in left segment, recursively quickSort left segment
Time complexity
N = list length
each subsequent quicksort will scan half of the original segment
we got N + 1/2N + 1/4N + ... + 1 = 2N - N/2^N (summation formula for geometric sequence)
the upper bound part is 2N, so it is O(N) time complexity
