Loading...
Loading...
Loading...
After a college coding contest, the results page shows n scores in no particular order. The placement coordinator wants the k-th largest score: if you sort the scores from high to low, it is the score at position k.
Equal scores count as separate entries. So in the scores 95, 95, 88, the second largest is 95, not 88.
Example 1
Input
6 2 72 95 88 95 60 81
Output
95
From high to low the scores are 95, 95, 88, 81, 72, 60. Position 2 holds the second 95.
Example 2
Input
5 3 40 75 90 55 68
Output
68
From high to low: 90, 75, 68, 55, 40. Position 3 holds 68.
Try the problem first. Open one hint at a time.
You do not need the whole list sorted. You only need the k largest scores seen so far.
Keep those k scores in a heap where the smallest of them is on top.
When the heap grows past k scores, remove the smallest one. It can never be the answer.
After all scores are read, the top of the heap is the k-th largest.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor