Task
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
Example 1:
1
2
3
4
|
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
|
Example 2:
1
2
3
4
|
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
|
Solution
- 要求时间复杂度是O(log(m+n))，应该用二分查找
- 使用二分查找来找到合并后的数组左侧一半来自原来两个数组的那些部分（下图黄色）：
- 首先计算合并后数组的长度，得到中点位置k
- 对第一个数组二分查找点m，第一个数组左侧的m个元素和第二个数组左侧的k-m个元素一同构成合并后数组左侧的k个元素（如下图）
- 对边界情况的讨论比较复杂，需考虑的情形很多
时间复杂度：在较短的数组中做二分查找，故O(log(min{m,n}))空间复杂度：O(1)- 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// Runtime: 44 ms, faster than 64.79% of C++ online submissions for Median of Two Sorted Arrays.
// Memory Usage: 89 MB, less than 58.39% of C++ online submissions for Median of Two Sorted Arrays.
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
long long n1=nums1.size(),n2=nums2.size();
//确保第一个数组长度更小，否则在二分时可能使第二个数组的索引值k-m1为负数
if(n1>n2)
return findMedianSortedArrays(nums2,nums1);
//合并后数组的中点左侧有k个元素
int k=(n1+n2+1)/2;
//二分查找，找到合并后数组左侧元素的来源
int l=0,r=n1;
while(l<r){
int m1=l+(r-l)/2,m2=k-m1;
if(nums1[m1]<nums2[m2-1])
l=m1+1;
else
r=m1;
}
//第一个数组前m1个元素和第二个数组前m2个元素组成合并后数组的前k个元素
int m1=l,m2=k-m1;
//考虑边界情形：可能合并后数组的前k个元素中不含有合并前某个数组的元素
double c1=max(m1<=0?INT_MIN:nums1[m1-1],
m2<=0?INT_MIN:nums2[m2-1]);
//考虑边界情形：合并前某个数组可能全部在合并后数组的前k个元素中
double c2=min(m1>=n1?INT_MAX:nums1[m1],
m2>=n2?INT_MAX:nums2[m2]);
//奇偶分开求中位数
if((n1+n2)%2==1)
return c1;
else
return (c1+c2)/2;
}
};
|