1117. Median in Linear Time
A weather station logs one temperature reading per minute and stores the readings in the array nums in the order they arrived. To report a typical value, the station wants the median reading: the value that would sit in the middle if all readings were sorted from the smallest to the largest. When the number of readings is even, there are two middle positions and the station uses the lower one, that is, the element at position (n - 1) / 2 (integer division, counting from 0) of the sorted order.
Return that median. Readings can repeat, and the station logs hundreds of thousands of them, so sorting everything is more work than needed.
Example 1
- Input:
- nums = [7,2,9,4,5]
- Output:
- 5
- Explanation:
Sorted, the readings are 2, 4, 5, 7, 9, and the middle one is 5.
Example 2
- Input:
- nums = [8,1,6,3]
- Output:
- 3
- Explanation:
Sorted: 1, 3, 6, 8. There are two middle values, 3 and 6, and the lower one, 3, is returned.
Constraints
1 ≤ nums.length ≤ 2 * 105
-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,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n) expected
- Space
- O(n)