leetcode 4寻找两个有序数组的中位数

最优解O(log(min(m,n)))

/**

之前用合并有序数组的思想做了O((m+n+1)/2),现在试一试O(log(min(m,n)))

基本思路为：通过二分查找较小的数组得到对应的中位数（假设存在，越界的情况最后套路）

假设分别为n1,n2,必有n1<=n2，假设最后找的两个可能的中位数是m1，m2个数（还是先假设存在）

那么二分查找nums1时，初始值left=0，right=n1；则m1 有[0,n1],m2有[k-n1,n1](k-n1>=0必然成立)

而n1<=n2，所以m2一定在[0,n2]之间，因此遍历小数组并不需要担心越界的事情，只需要在最后处理0和n1，n2的特殊情况；

***/

class Solution {

public:

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

        //首先检测是否是小数组在前，大数组在后

        const int n1=nums1.size();

        const int n2=nums2.size();

        if(n1>n2) return findMedianSortedArrays(nums2,nums1);

        int m1,m2;

        int left=,right=n1,k=(n1+n2+)/;

        //二分查找m1,m2（假设存在）

        while(left<right){

            m1=left+(right-left)/;

            m2=k-m1;

            if(nums1[m1]<nums2[m2-])

                left=m1+;

            else

                right=m1;

        }

        m1=left;

        m2=k-m1;

        int c1,c2;

        //找到第一个数c1，如果总共为奇数个，返回结果

        c1=max(m1<=?INT_MIN:nums1[m1-],m2<=?INT_MIN:nums2[m2-]);

        if((n1+n2)&==)

            return c1;

        //找到第二个数c2,并返回(c1+c2)/2

        c2=min(m1>=n1?INT_MAX:nums1[m1],m2>=n2?INT_MAX:nums2[m2]);

        return double(c1+c2)*0.5;

    }

};

方法二：合并有序数组

O(log(m+n+1)/2)

class Solution {

public:

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

        //time O(m+n+1)/2 space O(n)的解，获得两个num1的size（），分别用两个指针指向两个数组，每次把较小的向后移位

        int n1=nums1.size();int n2=nums2.size();

        int id1,id2;

        int mid=(n1+n2+)/;

        int i=,j=;

        int cur=INT_MIN;

        while(mid!=&&i<n1&&j<n2){

            mid--;

            if(nums1[i]<nums2[j])

                id1=nums1[i++];

            else

                id1=nums2[j++];

        }

        while(mid!=&&i<n1){

            mid--;

            id1=nums1[i++];

        }

        while(mid!=&&j<n2){

            mid--;

            id1=nums2[j++];

        }

        if((n1+n2)%==) return id1;

        id2=min((j>=n2?INT_MAX:nums2[j]),(i>=n1?INT_MAX:nums1[i]));

        return double(id1+id2)*0.5;

    }

};

附上二分法的分析过程：

总结一下：

1.   m1<=0时，c1=nums2[m2-1]，在4不成立时，c2=min(nums1[m1],nums2[m2])；

2.   m2<=0时，c1=nums1[m1-1]，c2=nums2[m2]，此时实际上m2=0，m1=n1而且n1=n2=k；

3.   m1>=n1，c2=nums2[m2]，在2不成立时，c1=max(nums1[m1-1],nums2[m2-1])；

4.   m2>=n2，c2=nums1[m1]，c1=nums2[m2-1]，此时实际上m1=0，m2=n2而且n1=n2=k；

因此容易理解的返回可以这么写

//

if(m2<=){//此时m1>=n1成立

    c1=nums1[m1-],c2=nums2[m2];

}

//

if(m2>=n2){//此时m1<=0成立

    c1=nums2[m2-],c2=nums1[m1];

}

//

if(m1<=){

    c1=nums2[m2-],c2=min(nums1[m1],nums2[m2]);

}

//

if(m1>=n1){

    c1=max(nums1[m1-],nums2[m2-]),c2=nums2[m2];

}

//对于c1，可知当m1<=0成立时应该选nums2[m2-1]（2、3），当m2<=0成立时应该选择nums1[m1-1]（1），当两个都不成立取两者最大值（4），由于题给条件两者不可能都成立除非nums1，nums2都为空

c1=max(m1<=?INT_MIN:nums1[m1-],m2<=?INT_MIN:nums2[m2-]);

//对于c2，可知当m1>=n1成立时应该选nums2[m2](1、4)，当m2>=n2成立时应该选择nums1[m1](2)，当两者都不成立时取最小值（3），同样由于提给条件两者不可能都成立；

c2=min(m1>=n1?INT_MAX:nums1[m1],m2>=n2?INT_MAX:nums2[m2]);

leetcode 4寻找两个有序数组的中位数的相关教程结束。