题目：

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)/2+1);        }        else        {            return ( Solution::find_kth(A,m,B,n,(m+n)/2) + Solution::find_kth(A,m,B,n,(m+n)/2+1) ) / 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==0) return B[k-1];        if (k==1) return std::min(A[0],B[0]);        // binary search        int pos_A = std::min(k/2,m);        int pos_B = k - pos_A;        if (A[pos_A-1] < B[pos_B-1])        {            return Solution::find_kth(A+pos_A, m-pos_A, B, n, k-pos_A);        }        else if (A[pos_A-1] > B[pos_B-1])        {            return Solution::find_kth(A, m, B+pos_B, n-pos_B, k-pos_B);        }        else        {            return A[pos_A-1];        }    }};

 

Tips:

1. 采用二分查找，需要判断一下边界条件。

2. 这里用到一个技巧，始终保证m小于n，如果不满足就做一次转换

========================================

第二次过这道题，OJ的接口已经改成vector的了。

第一遍能记得大概的思路，但是涉及到边界细节，还是有些无力。

class Solution {public:    double findMedianSortedArrays(vector
     
      & nums1, vector
      
       & nums2) {            const int m = nums1.size();            const int n = nums2.size();            int k = m+n;            if ( k & 1 ) // odd            {                return Solution::findMedian(nums1, 0, m-1, nums2, 0, n-1, (m+n)/2+1);            }            else // even            {                return (                     Solution::findMedian(nums1,0, m-1, nums2, 0, n-1, (m+n)/2) +                     Solution::findMedian(nums1, 0, m-1, nums2, 0, n-1, (m+n)/2+1) ) /2.0;            }    }    static double findMedian(            vector
       
        & nums1, int begin1, int end1,            vector
        
         & 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-1];            if ( k==1 ) return std::min(nums1[begin1], nums2[begin2]);            // recursive branchs            int local1 = std::min(k/2, end1-begin1+1);            int local2 = k-local1;            if ( nums1[begin1+local1-1]
         
          nums2[begin2+local2-1] )            {                return Solution::findMedian(nums1, begin1, end1, nums2, begin2+local2, end2, local1);            }            else            {                return nums1[begin1+local1-1];            }    }};
         
        
       
      
     

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了，但还是觉得受益。