Loading...
Loading...
Loading...
Two sections of a class sent their test scores to the head of department. Each section's list is already sorted from low to high. The head wants the median of all scores together: the middle score after putting everything in order.
If the total count is odd, the median is the middle score. If it is even, the median is the average of the two middle scores. Print it exactly: a whole number, or a number ending in .5 (such as 2.5 or -0.5).
.5.Example 1
Input
2 3 1 3 2 4 5
Output
3
All scores in order: 1 2 3 4 5. The middle one is 3.
Example 2
Input
2 2 1 2 3 4
Output
2.5
In order: 1 2 3 4. The average of 2 and 3 is 2.5.
Try the problem first. Open one hint at a time.
Merging both lists works in O(n + m). Try to do better: think of a cut that splits the scores into a left half and a right half.
If you take i scores from the first list, the left half needs exactly (n + m + 1) / 2 - i scores from the second list.
The cut is right when the largest score on the left of each list is at most the smallest score on the right of the other list.
Search i over the shorter list. Use very small and very large values when a side is empty, and add the two middle scores in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor