Eg. array = [1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67] nth_largest( array, 2) = 55 nth_largest( array, 5) = 9
You can make the vector into a heap in O(n). You can take from the heap in O(lg n). You have to take k elements to find the k-th largest. Therefore, this can be done in O(n + k lg n) with k < n, which is a lower bound than O(n lg n) (sorting).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.