1347. Trimmed Total
A talent show panel scores each act with an integer and, to reduce bias, throws away the k lowest scores and the k highest scores before adding up what is left. Scores are in the array nums. Duplicates are counted separately by sorted position: if the lowest score appears three times and k is 2, exactly two of those copies are discarded and one stays.
Return the sum of the remaining n - 2k scores as a 64-bit integer, since the total can exceed 32 bits. It is guaranteed that 2k is smaller than n, so at least one score remains. Sorting gives O(n log n) time; finding the two cut values with quickselect is an O(n) alternative.
Example 1
- Input:
- nums = [5,1,9,3,7], k = 1
- Output:
- 15
- Explanation:
The sorted array is 1, 3, 5, 7, 9. Dropping the smallest and the largest leaves 3 + 5 + 7 = 15.
Example 2
- Input:
- nums = [4,4,4,4,4], k = 2
- Output:
- 4
- Explanation:
After dropping two from each end only one element, 4, is left.
Example 3
- Input:
- nums = [-5,10,0], k = 1
- Output:
- 0
- Explanation:
The sorted array is -5, 0, 10, so only 0 remains.
Constraints
- 1 ≤ n ≤ 1000, where n is the length of
nums - 0 ≤ k and 2 * k < n
- -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 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)