Question
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(lgn)
- 将第一个数组划分成两部分
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
- 将第二个数组划分成两部分
left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
- 两个左半部分小于两个右半部分
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
- 条件
1) len(left_part) == len(right_part)
2) max(left_part) <= min(right_part)
我们可以看到因为左右的长度一样，都等于两个数组长度之和的一半。所以i的位置确定，那么j的位置也确定了，所以我们只需要找一个合适的i，使得满足以上两个条件就可以了。
Code
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
if (m > n) {
vector<int> tmp = nums1;
nums1 = nums2;
nums2 = tmp;
m = nums1.size();
n = nums2.size();
}
if (m == 0) {
if (n % 2 == 1) {
return nums2[n / 2];
} else {
return ( nums2[n / 2 - 1] + nums2[n / 2] ) / 2.0;
}
}
int imin = 0;
int imax = m;
// 因为可能是奇数个，所以得加1
int half_len = (m + n + 1) / 2;
while (imin <= imax) {
int i = (imin + imax) >> 1;
int j = half_len - i;
// 说明i太大了，需要减小
if (i > 0 && nums1[i - 1] > nums2[j]) {
imax = i - 1;
}
// 说明i太小了，需要增大
else if (i < m && nums2[j - 1] > nums1[i]) {
imin = i + 1;
}
else {
int left_max;
int right_min;
// i等于0，说明nums1，全属于右边
if (i == 0) left_max = nums2[j - 1];
// j等于0，说明nums2，全属于右边
else if (j == 0) left_max = nums1[i - 1];
else left_max = max(nums1[i - 1], nums2[j - 1]);
if ((m + n) % 2 == 1)
return left_max;
// i等于m说明nums1，全属于左边
if (i == m) right_min = nums2[j];
// j等于n说明nums2，全属于左边
else if (j == n) right_min = nums1[i];
else right_min = min(nums1[i], nums2[j]);
return (left_max + right_min) / 2.0;
}
}
}
};