348. Middle of Two Shelves
Two warehouses each keep their crate weights in a sorted list. Management wants the median weight of all the crates taken together, as if the two lists had been merged into one sorted list. If the total number of crates is odd, the median is the middle weight; if it is even, it is the average of the two middle weights.
Given the sorted arrays a and b, return that median as a decimal number. Merging the lists is O(m + n) and not good enough: your solution has to run in O(log(min(m, n))) time. One of the two lists may be empty, but not both.
Example 1
- Input:
- a = [1,3,8], b = [2,9]
- Output:
- 3
- Explanation:
The merged list is [1, 2, 3, 8, 9], so the median is the middle value 3.
Example 2
- Input:
- a = [4,6], b = [5,7]
- Output:
- 5.5
- Explanation:
The merged list is [4, 5, 6, 7]; the two middle values are 5 and 6, so the median is 5.5.
Constraints
0 ≤ a.length, b.length ≤ 106, and a.length + b.length ≥ 1
-109 ≤ a[i], b[i] ≤ 109
Both arrays are sorted in non-decreasing order.
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(log(min(m, n)))
- Space
- O(1)