4. Median of Two Sorted Arrays
Problem:
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Solution:
O(log (m+n)) means half of the sequence is ruled out on each loop. So obviously we need binary search.
To do it on two sorted arrays, we need a formula to guide division.
Let nums3
be the sorted array combining all the items in nums1
and nums2
.
If nums2[j-1] <= nums1[i] <= nums2[j]
, then we know nums1[i]
is at num3[i+j]
. Same goes nums1[i-1] <= nums2[j] <= nums1[i]
.
Let k
be ⌊(m+n-1)/2⌋
. We need to find nums3[k]
(and also nums3[k+1]
if m+n is even).
Let i + j = k
, if we find nums2[j-1] <= nums1[i] <= nums2[j]
or nums1[i-1] <= nums2[j] <= nums1[i]
, then we got k
.
Otherwise, if nums1[i] <= nums2[j]
then we know nums1[i] < nums2[j-1]
(because we did not find k
).
- There are
i
items beforenums1[i]
, andj-1
items brefornums2[j-1]
, which meansnums1[0...i]
are beforenums3[i+j-1]
. So we now knownums1[0...i] < nums3[k]
. They can be safely discarded. - We Also have
nums1[i] < nums2[j]
, which meansnums2[j...n)
are afternums3[i+j]
. Sonums2[j...n) > nums3[k]
.
Same goes nums1[i-1] <= nums2[j] <= nums1[i]
.
☆: .。. o(≧▽≦)o .。.:☆☆: .。. o(≧▽≦)o .。.:☆