Kth Largest Element in an Array
MediumHeap · Adobe
Given an integer array nums and an integer k, return the k-th largest element in the array.
This means the element that would be at position k (1-indexed) if nums were sorted from largest to smallest. It is *not* the k-th largest distinct value: duplicates each take up their own position.
Try to solve it without fully sorting the array.
Example 1
- Input:
- nums = [7, 2, 9, 4, 9, 1], k = 3
- Output:
- 7
- Explanation
- Sorted from largest to smallest the values are
9, 9, 7, 4, 2, 1. Both 9s count, so the 3rd largest is 7, not 4.
Example 2
- Input:
- nums = [5, -2, 8, -6], k = 4
- Output:
- -6
- Explanation
- When
kequals the array length, the answer is the smallest value, -6.
Example 3
- Input:
- nums = [3, 3, 3, 1], k = 2
- Output:
- 3
- Explanation
- The two largest positions are both filled by 3, so the 2nd largest is 3.
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4