LeetCode 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)).
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
解析：
给定两个有序数组，找到这两个数组的中位数。
并且限定时间复杂度为O(log (m+n))。
方法1:
如果不考虑时间复杂度，可以对两个有序数组进行归并排序，然后选择排序后的中位数，时间复杂度为\(O(m+n)\)。此解法在这里不符合要求。
方法2:
考虑到时间复杂度为O(log (m+n))，想到可以采用二分查找的思想。
假设A数组长度为m，B数组长度为n，总长度为total=m+n,如果total为奇数，则查找第（total/2+1）个数；如果为偶数，则查找的为第（total/2）和(total/2+1)个数的平均值。
假设A和B的元素个数都大于k/2,我们将A的k/2个元素（A[k/2-1]）和B的第k/2个元素(B[k/2-1])进行比较，有如下三种情况：
A[k/2-1]==B[k/2-1]
A[k/2-1] > B[k/2-1]
A[k/2-1] < B[k/2-1]
如果A[k/2-1] < B[k/2-1]意味着A[0]到A[k/2-1]肯定在A，B合并后的topk元素的范围内，即A[k/2-1]不可能大于A，B合并后的第K大元素，因此我们可以删除A数组的这k/2个元素。
同理，当A[k/2-1] > B[k/2-1]时，我们可以删除B数组的k/2个元素。
当A[k/2-1]==B[k/2-1]，说明找到了第k大的元素。
[cc lang=”C++”]
class Solution {
public:
double findMedianSortedArrays(vector
const int m = nums1.size();
const int n = nums2.size();
int total = m + n;
if(total %2==1)//总长度是奇数
{
return find_kth(nums1.begin(), m, nums2.begin(), n, total/2+1);
}else//总长度是偶数
{
return (find_kth(nums1.begin(), m, nums2.begin(), n, total/2) + find_kth(nums1.begin(), m, nums2.begin(), n, total/2+1))/2.0;
}
}
private:
static int find_kth(std::vector
{
if(m > n)//假定A数组的长度小于等于B数组的长度
return find_kth(B,n,A,m,k);
if(m==0)//A数组为空时，返回B数组的第K个元素
return *(B + k-1);
if(k==1)//返回A[0],B[0]中较小的一个
return min(*A, *B);
int ia = min(k/2, m), ib = k – ia;
if(*(A+ia-1) < *(B+ib-1))
return find_kth(A+ia, m-ia,B,n,k-ia);
else if(*(A+ia-1) > *(B+ib-1))
return find_kth(A, m, B+ib, n-ib, k-ib);
else
return A[ia-1];
}
};
[/cc]
参考：
https://segmentfault.com/a/1190000002988010
https://www.cnblogs.com/grandyang/p/4465932.html
About Author
