1. 题目

004-Median_of_two_sorted_arrays

2. 算法

http://blog.csdn.net/yutianzuijin/article/details/11499917/

• 要求复杂度O(nlg(n+m))

* 思路

• 将原问题转换为一个寻找第k小数的问题

• 边界条件

3. 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total=nums1.size()+nums2.size();
        if(total &0x1)
            return findkth(nums1,nums2,total/2+1);
        else{
            vector<int>a,b;
            a.assign(nums1.begin(),nums1.end());
            b.assign(nums2.begin(),nums2.end());
            return (findkth(nums1,nums2,total/2)+findkth(nums1,nums2,total/2+1))/2.0;
        }

    }

    double findkth(vector<int>& A,vector<int>& B,int k){
        int m=A.size();
        int n=B.size();
        if(m>n)  return findkth(B,A,k);
        if(m==0)  return B[k-1];
        if(k==1)  return min(A[0],B[0]);

        int pa=min(k/2,m),pb=k-pa;
        if(A[pa-1]<B[pb-1]){
            A.erase(A.begin(),A.begin()+pa);
            return findkth(A,B,k-pa);
        }else if(A[pa-1]>B[pb-1]){
            B.erase(B.begin(),B.begin()+pb);
            return findkth(A,B,k-pb);
        }else{
            return A[pa-1];
        }
    }
};