225. Kth Heaviest
A port weighs a long row of containers, and the weights are stored in the array nums. Several containers may have the same weight. Imagine the weights sorted from heaviest to lightest, equal weights included separately. Return the weight in position k of that list, counting from 1.
For instance, for weights [7, 7, 5, 2] the heaviest is 7, the second heaviest is 7 again, the third heaviest is 5 and the fourth is 2.
The row can contain up to 100,000 containers and k can be anywhere from 1 to the length of the row, so removing the heaviest container k times is far too slow. Try to find the answer in linear time on average, without fully sorting.
Example 1
- Input:
- nums = [14,3,9,3,21,9,5], k = 3
- Output:
- 9
- Explanation:
Sorted from heaviest: 21, 14, 9, 9, 5, 3, 3. The third entry is 9.
Example 2
- Input:
- nums = [4,4,4], k = 3
- Output:
- 4
- Explanation:
All weights are equal, so the third heaviest is 4.
Example 3
- Input:
- nums = [-7,12,0,-7,5], k = 5
- Output:
- -7
- Explanation:
Sorted from heaviest: 12, 5, 0, -7, -7. The fifth entry is -7.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ k ≤ nums.length
-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n) average
- Space
- O(1) extra