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)).

思路

如果不要求为log的时间复杂度，则可以用遍历的方式，从两个数组的开始同，合并两个已排序链表的方式，找到k，

解法一：

求中值也就是求倒数第K=（m+n）/2的值，

int findkth(vector<int>::iterator nums1,int m,vector<int>::iterator nums2,int n,int k){

        if(m>n){

            return findkth(nums2,n,nums1,m,k);

        }

        if(m==0)

            return *(nums2+k-1);

        if(k==1)

            return min(*nums1,*nums2);

        else{

            int ia=min(m,k/2);

            int ib=k-ia;

            if(*(nums1+ia-1)<*(nums2+ib-1)){

                return findkth(nums1+ia,m-ia,nums2,n,k-ia);

            }

            else if(*(nums1+ia-1)>*(nums2+ib-1))

                return findkth(nums1,m,nums2+ib,n-ib,k-ib);

            else

                return *(nums1+ia-1);

        }

    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        int m=nums1.size();

        int n=nums2.size();

        int total=m+n;

        int k=total/2;

        if(total%2)

            return findkth(nums1.begin(),m,nums2.begin(),n,k+1);

        else

            return (findkth(nums1.begin(),m,nums2.begin(),n,k+1)+findkth(nums1.begin(),m,nums2.begin(),n,k))/2.0;

    }

Median of Two Sorted Arrays

原文：http://searchcoding.blog.51cto.com/1335412/1693322