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

c++归并算法 v1.0 奇偶分开

class Solution
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int n1=nums1.size();
        int n2=nums2.size();
        int k=n1+n2;
        int a[k];
        int m=0,n=0;
        if(k%2==1)
        {
                int i=0;
                while(m<n1&&n<n2)
                    if(nums1[m]<=nums2[n])
                    {
                        a[i++]=nums1[m++];
                    }
                    else
                    {
                        a[i++]=nums2[n++];
                    }
                while (m<n1)
                {
                    a[i++]=nums1[m++];
                    if(i==k/2+1)
                        break;
                }

                while(n<n2)
                {
                    a[i++]=nums2[n++];
                    if(i==k/2+1)
                        break;
                }

            return a[k/2];
        }
        else
        {
                int i=0;
                while(m<n1&&n<n2)
                    if(nums1[m]<=nums2[n])
                    {
                        a[i++]=nums1[m++];//可能越界
                    }
                    else
                    {
                        a[i++]=nums2[n++];
                    }
                while (m<n1)
                {
                    a[i++]=nums1[m++];
                    if(i==k/2+1)
                        break;
                }

                while(n<n2)
                {
                    a[i++]=nums2[n++];
                    if(i==k/2+1)
                        break;
                }

            return (a[k/2-1]+a[k/2])/2.0;
        }


    }
};

c++归并算法 v2.0 奇偶合并

class Solution
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int n1=nums1.size();
        int n2=nums2.size();
        int k=n1+n2;
        int a[k];
        int m=0,n=0;

        int i=0;
        while(m<n1&&n<n2)
            if(nums1[m]<=nums2[n])
            {
                a[i++]=nums1[m++];//可能越界
            }
            else
            {
                a[i++]=nums2[n++];
            }
        while (m<n1)
        {
            a[i++]=nums1[m++];
            if(i==k/2+1)
                break;
        }

        while(n<n2)
        {
            a[i++]=nums2[n++];
            if(i==k/2+1)
                break;
        }
        return (a[(k-1)/2]+a[k/2])/2.0;

    }
};

python

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n1=len(nums1)
        n2=len(nums2)
        num=n1+n2
        m=0
        n=0
        i=0
        ans=[]
        while(m<n1 and n<n2):
            if(nums1[m]<=nums2[n]):
                ans.append(nums1[m])
                m+=1
            else:
                ans.append(nums2[n])
                n+=1
        while(m<n1):
            ans.append(nums1[m])
            m+=1
        while(n<n2):
            ans.append(nums2[n])
            n+=1
        return (ans[(num-1)/2]+ans[num/2])/2.0

注意事项

1.原先想在最外层套用的是for循环，好在中途就退出减少使用时间，但是i并不容易控制，所以最后还是用了while循环，使得i的控制随心所欲
2.无论奇数偶数，使用(a[(k-1)/2]+a[k/2])/2.0都是一样的，数量为奇数的话都是本身，数量偶数的话就是中间前一个加后一个
3.最坏时间复杂度为O(m+n)，仍然没达到题目要求