101
0/320
Loading content...
You are given an unsorted integer array nums and a positive integer k. Your task is to determine the element that would occupy the k-th position if the array were sorted in descending order (from largest to smallest).
In other words, find the k-th largest value in the collection. Note that this refers to the k-th largest element based on the sorted position, accounting for the element's rank when duplicates are present. For instance, if k = 2, you need to find the second largest element, which may have the same value as another element in the array.
Challenge: Can you devise a solution that achieves better than O(n log n) average time complexity without fully sorting the array?
nums = [3,2,1,5,6,4]
k = 25When sorted in descending order, the array becomes [6,5,4,3,2,1]. The element at position 2 (1-indexed) is 5, making it the 2nd largest element.
nums = [3,2,3,1,2,4,5,5,6]
k = 44Sorted in descending order: [6,5,5,4,3,3,2,2,1]. The 4th element is 4. Notice that duplicates occupy their own positions in the sorted sequence.
nums = [1,2,3,4,5]
k = 33In descending order: [5,4,3,2,1]. The element ranked 3rd is 3.
Constraints