You get two sorted vectors of integers, nums1 and nums2. Return the median of all their numbers together.
The median is the middle number when all the numbers are in order. With an even count, there are two middle numbers. Then the median is their average.
Each vector goes from smallest to largest. One of them can be empty, but not both.
The tests keep a few big vectors. They call your solution on many pairs of them. Don't change the vectors you get.
Each answer is printed with one digit after the point, like 9.0 or 2.5.
Example 1:
Input: nums1 = [4,9,15], nums2 = [6,11] Output: 9.0 Explanation: Sorted together, they make [4,6,9,11,15]. The middle one is 9.
Example 2:
Input: nums1 = [-5,0,3,8], nums2 = [1,2,12,20] Output: 2.5 Explanation: Sorted together, they make [-5,0,1,2,3,8,12,20]. The two middle ones are 2 and 3. Their average is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [], nums2 = [7,10] Output: 8.5 Explanation: nums1 is empty. The median of 7 and 10 is (7 + 10) / 2 = 8.5.
Constraints:
- Each vector has 0 to 100,000 numbers.
- At least one of them is not empty.
- Each number is from -106 to 106.
- Both vectors are sorted from smallest to largest.
- One test makes up to 10,000 calls.
Your solution should run in O(log(min(m, n))) time, where m and n are the two lengths.
Picture a cut through each vector. The two left parts together hold half of all the numbers. If no number on the left is bigger than a number on the right, the median sits at the cut.
Say the left part takes
i numbers from the shorter vector. The rest of the half comes from the other one. Binary search on i. When the shorter vector's last left number is too big, i is too big.
Each try halves the range of
i, which starts as 0 to the shorter length: O(log(min(m, n))) time.A merge of the two vectors would take O(m + n) time for each call. With 10,000 calls, that is too slow.
Only a few numbers are kept, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
