题目：
There are two sorted arrays A and B 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)).
代码：
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
int total = m+n;
if(total & 0x1)
{
return Solution::find_kth(A,m,B,n,(m+n)/+);
}
else
{
return ( Solution::find_kth(A,m,B,n,(m+n)/) + Solution::find_kth(A,m,B,n,(m+n)/+) ) / 2.0;
}
}
static int find_kth(int A[], int m, int B[], int n, int k)
{
// make sure m is less or equal than n
if(m>n) return find_kth(B,n,A,m,k);
// finish conditions
if (m==) return B[k-];
if (k==) return std::min(A[],B[]);
// binary search
int pos_A = std::min(k/,m);
int pos_B = k - pos_A;
if (A[pos_A-] < B[pos_B-])
{
return Solution::find_kth(A+pos_A, m-pos_A, B, n, k-pos_A);
}
else if (A[pos_A-] > B[pos_B-])
{
return Solution::find_kth(A, m, B+pos_B, n-pos_B, k-pos_B);
}
else
{
return A[pos_A-];
}
}
};Tips:
1. 采用二分查找，需要判断一下边界条件。
2. 这里用到一个技巧，始终保证m小于n，如果不满足就做一次转换
========================================
第二次过这道题，OJ的接口已经改成vector的了。
第一遍能记得大概的思路，但是涉及到边界细节，还是有些无力。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const int m = nums1.size();
const int n = nums2.size();
int k = m+n;
if ( k & ) // odd
{
return Solution::findMedian(nums1, , m-, nums2, , n-, (m+n)/+);
}
else // even
{
return (
Solution::findMedian(nums1,, m-, nums2, , n-, (m+n)/) +
Solution::findMedian(nums1, , m-, nums2, , n-, (m+n)/+) ) /2.0;
}
}
static double findMedian(
vector<int>& nums1, int begin1, int end1,
vector<int>& nums2, int begin2, int end2,
int k
)
{
// make sure "end1-begin1" <= "end2-begin2"
if ( end1-begin1 > end2-begin2 )
{
return Solution::findMedian(nums2, begin2, end2, nums1, begin1, end1, k);
}
// finish conditions
if ( begin1>end1 ) return nums2[begin2+k-];
if ( k== ) return std::min(nums1[begin1], nums2[begin2]);
// recursive branchs
int local1 = std::min(k/, end1-begin1+);
int local2 = k-local1;
if ( nums1[begin1+local1-]<nums2[begin2+local2-] )
{
return Solution::findMedian(nums1, begin1+local1, end1, nums2, begin2, end2, local2);
}
else if ( nums1[begin1+local1-]>nums2[begin2+local2-] )
{
return Solution::findMedian(nums1, begin1, end1, nums2, begin2+local2, end2, local1);
}
else
{
return nums1[begin1+local1-];
}
}
};tips：
主要是几个细节
1. 长度是奇数和偶数要分别处理：对于奇数长度的median就是中间的那个元素；对于偶数长度的median就是中间那两个位置元素的均值
2. 既然是递归就一定要有终止条件，这里的终止条件有两个：
a) 有一个数组走到头了
b) 还需要挑出来的元素个数为1（即k==1）
遇上上述两个条件，递归可以不用往下进行了。
3. 还是强调一个技巧，需要判断两个数组长短的时候，不如再一开始就限定好传进来的哪个数组长，哪个数组短
即，
// make sure "end1-begin1" <= "end2-begin2"
if ( end1-begin1 > end2-begin2 )
{
return Solution::findMedian(nums2, begin2, end2, nums1, begin1, end1, k);
}
这样一来就省去了很多的代码（比如已经知道了nums1的长度一定小于nums2的长度，就可以得到local1了）
4. 以前有个思维限制，既然binary search就一定要每次排除k个，那么nums1要排除k/2个，nums2要排除k/2个喽。。。这是个比较大的思维误区，由于是两个数组，每个多长都不一定，不一定两个数组都干掉相同长度；况且，k可能是奇数或者偶数，讨论起来特别麻烦。
因此，干脆确定短的一个数组往后推的长度，再用总共需要挑出来的数字减去数组一用过的长度，剩下的就是第二个数组可以往后推的长度了。
这道题非常好 思路+细节都有值得学习的地方，虽然是第二次AC了，但还是觉得受益。