# 4. Median of Two Sorted Arrays
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)).
You may assume nums1 and nums2 cannot be both empty.
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
Approach 1: use 2 pointers to merge 2 sorted arrays, counting items up until the (M + N) / 2
th. Running time O(M + N)
, where M and N are the array lengths.
Approach 2: for each item in nums1, find its insert position in nums2 (using binary search), and see if insert position_in_nums2 + its_own_index_in_nums1 == (M + N) / 2
. Do the same for each item in nums2 (insert back to nums1). If M + N is even, then look for 2 numbers: (M + N) / 2
and (M + N) / 2 + 1
, then take the average. Running time O(Mlog(N)) + O(Nlog(M))
.
Approach 3: Solve the problem of finding the kth smallest element in 2 sorted arrays. This can be done by comparing the the k/2th smallest items in both arrays, then eliminating k/2 items from one of the arrays. Running time O(log(M + N))
.
# Code (Python)
Approach 3:
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
if (len(nums1) + len(nums2)) % 2 == 1:
return self.find_kth_smallest_in_two_sorted_arrays(
nums1,
nums2,
(len(nums1) + len(nums2)) // 2 + 1
)
else:
return (
self.find_kth_smallest_in_two_sorted_arrays(
nums1,
nums2,
(len(nums1) + len(nums2)) // 2
) +
self.find_kth_smallest_in_two_sorted_arrays(
nums1,
nums2,
(len(nums1) + len(nums2)) // 2 + 1
)
) / 2
def find_kth_smallest_in_two_sorted_arrays(self, nums1, nums2, k):
# make sure nums1 is shorter than nums2
if len(nums1) > len(nums2):
return self.find_kth_smallest_in_two_sorted_arrays(nums2, nums1, k)
# 2 base cases
if len(nums1) == 0:
return nums2[k-1]
if k == 1:
return min(nums1[0], nums2[0])
# eliminates roughly k/2 items each time by comparing the k/2 smallest item in each array
index1 = min(len(nums1), k // 2)
index2 = k - index1
if nums1[index1 - 1] <= nums2[index2 - 1]:
# rule out nums1[0:index1], because nums1[index1-1] is at most larger than 2 * (k/2 - 1) items, so it can't be the kth smallest in both arrays combined
# should really pass just the start index and not do this array slicing, because slicing takes linear time
return self.find_kth_smallest_in_two_sorted_arrays(nums1[index1:], nums2, index2)
else:
return self.find_kth_smallest_in_two_sorted_arrays(nums1, nums2[index2:], index1)
# Code (C++)
Approach 1:
// O(m+n)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size();
int n2 = nums2.size();
vector<int> res;
int i1 = 0;
int i2 = 0;
while (i1 < n1 || i2 < n2)
{
if (i1 >= n1 || (i2 < n2 && nums1[i1] > nums2[i2]))
{
res.push_back(nums2[i2]);
i2++;
}
else
{
res.push_back(nums1[i1]);
i1++;
}
}
int n3 = res.size();
if (n3 % 2 != 0)
return res[n3/2];
else
return (double)(res[n3/2] + res[n3/2-1]) / 2;
}
};
Approach 3:
// O(log(m+n))
class Solution {
private:
int getKth(vector<int>& nums1, vector<int>& nums2, int head1, int head2, int k) {
if (head1 >= nums1.size())
return nums2[head2+k-1];
if (head2 >= nums2.size())
return nums1[head1+k-1];
if (k == 1)
return std::min(nums1[head1], nums2[head2]);
if (head2+k/2-1 >= nums2.size() ||
head1+k/2-1 < nums1.size() && nums1[head1+k/2-1] <= nums2[head2+k/2-1])
return getKth(nums1, nums2, head1+k/2, head2, k-k/2);
else
return getKth(nums1, nums2, head1, head2+k/2, k-k/2);
}
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
if (len % 2 != 0)
return getKth(nums1, nums2, 0, 0, len/2+1);
else
return (double)(
getKth(nums1, nums2, 0, 0, len/2) +
getKth(nums1, nums2, 0, 0, len/2+1))
/ 2;
}
};