- Update: I keep forgetting how to solve it in
O(log(m+n)), so I’ll just stick to
double pointerway. Be careful of edge cases like one of them is empty or they have same elements like
- It requires
O(log(m+n))time complexity, apparently, we need
- How to find the
median? The median separates the array in half.
- For convenience, we use binary search on the shorter array between nums1 and nums2. If nums2 is shorter than nums1, we swtich them.
- First, we get the
index of medianof
(start + end) >> 1. Here, both operands are indexes. By basic math, the cut point in nums2 should be
half - i - 2. Half is the half length of nums1 and nums2 together, we substract (i+1) from it, which is the
first partof nums1. But because we need
index, we still need to minus 1.
L1 = nums[i], R1 = nums[i+1].
L2 = nums[j], R2 = nums[j+1].
- When can we say we’ve found the result?
L1 <= R2 && L2 <= R1.
- What if we didn’t?
L1 > R2, we need to make
end = i - 1. If
L2 > R1, which means
L1is too short. We need to make i bigger,
start = i + 1.
- For example, when
L1 > R2, what would happen will be like
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be
Input: nums1 = [1,2], nums2 = [3,4]
Binary search with O(log(m+n))
Double pointers with O(m+n)