- We know we need to use some sort of
sortingalgo, but which one?
- Only in quick sort do we need know a pivot that can tell us how many bigger elements than the pivot.
- We don’t need to sort all elements, we need some
binary searchbased on whethere
pivotis bigger than
nums.length - k.
pivot < nums.length - k, it means the res is located in the
right. Then we do
quicksort(pivot + 1, right);
Given an integer array
nums and an integer
k, return the
kth largest element in the array.
Note that it is the
kth largest element in the sorted order, not the
kth distinct element.
Input: nums = [3,2,1,5,6,4], k = 2
Time complexity O(N)
N*(1/2 + 1/4 + ...) = N