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

这道题原理很简单，由中位数和时间要求O(logMN)可以很直接的想到用分治法来做，困难的地方在于边界条件，可能出现比较复杂的情况。为此我想到了一个比较简单来处理边界条件的方法就是在两串数的前后各加上无穷大和无穷小。这样既能防止数组越界又可以将几种边界条件统一为相同的判定。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()>nums2.size()){//令nums1为较短的数组防止j越界
            return findMedianSortedArrays(nums2,nums1);
        }
        double median;
        if(nums1.size()==0){//nums1为空时
            if(nums2.size()%2){
                return nums2[nums2.size()/2];
            }
            else{
                median=(double(nums2[nums2.size()/2-1]+nums2[nums2.size()/2]))/2;
                return median;
            }
        }
        vector<int> n1;
        vector<int> n2;
        n1.push_back(-2147483648);
        n2.push_back(-2147483648);
        n1.insert(n1.end(),nums1.begin(),nums1.end());
        n2.insert(n2.end(),nums2.begin(),nums2.end());
        n1.push_back(2147483647);
        n2.push_back(2147483647);
        int i,j,m1,m2,b1,e1;
        m1=n1.size();
        m2=n2.size();
        b1=0;
        e1=m1-2;//b1<=i<=e1，ij为划线左侧
        i=m1/2;
        j=(m1+m2)/2-i+(m1+m2)%2-2;
        while(n1[i]>n2[j+1]||n2[j]>n1[i+1]){
            if(n1[i]>n2[j+1]){//此时i应减小
                e1=i;
                i=i-(e1-b1)/2-(e1+b1)%2;
                j=j+(e1-b1)/2+(e1+b1)%2;
            }
            else{//此时i应增大
                b1=i;
                i=i+(e1-b1)/2+(e1+b1)%2;
                j=j-(e1-b1)/2-(e1+b1)%2;
            }
        }
        if((m1+m2)%2){//奇数为真，偶数为假
            median=n1[i]>n2[j]?n1[i]:n2[j];
        }
        else{
            double left=n1[i]>n2[j]?n1[i]:n2[j];
            double right=n1[i+1]<n2[j+1]?n1[i+1]:n2[j+1];
            median=(left+right)/2;
        }
        return median;
    }
};

可以看到虽然用了分治的方法但是并不够快，因为为了在头尾加负正无穷复制了一遍两个数组，等于增加了一遍对数组的遍历反而不如暴力解法。因此可以想到只需要在边界的时候将对应的元素指定为正负无穷即可。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()>nums2.size()){//令nums1为较短的数组防止j越界
            return findMedianSortedArrays(nums2,nums1);
        }
        double median;
        if(nums1.size()==0){//nums1为空时
            if(nums2.size()%2){
                return nums2[nums2.size()/2];
            }
            else{
                median=(double(nums2[nums2.size()/2-1]+nums2[nums2.size()/2]))/2;
                return median;
            }
        }
        int i,j,m1,m2,b1,e1,neginf,inf,n1_i,n1_iplus1,n2_j,n2_jplus1;
        neginf=-2147483648;
        inf=2147483647;
        m1=nums1.size();
        m2=nums2.size();
        b1=-1;
        e1=m1-1;//b1<=i<=e1，ij为划线左侧
        i=m1/2;
        j=(m1+m2)/2-i+(m1+m2)%2-2;
        n1_i=i==-1?neginf:nums1[i];
        n1_iplus1=i==m1-1?inf:nums1[i+1];
        n2_j=j==-1?neginf:nums2[j];
        n2_jplus1=j==m2-1?inf:nums2[j+1];
        while(n1_i>n2_jplus1||n2_j>n1_iplus1){
            if(n1_i>n2_jplus1){//此时i应减小
                e1=i;
                i=i-(e1-b1)/2-abs((e1+b1)%2);//这里添加绝对值是因为一些特殊情况时(b1=-1,e1=0)时
                                             //(e1+b1)%2为-1反而使i增大
                j=j+(e1-b1)/2+abs((e1+b1)%2);
            }
            else{//此时i应增大
                b1=i;
                i=i+(e1-b1)/2+abs((e1+b1)%2);
                j=j-(e1-b1)/2-abs((e1+b1)%2);
            }
            n1_i=i==-1?neginf:nums1[i];
            n1_iplus1=i==m1-1?inf:nums1[i+1];
            n2_j=j==-1?neginf:nums2[j];
            n2_jplus1=j==m2-1?inf:nums2[j+1];
        }
        if((m1+m2)%2){//奇数为真，偶数为假
            median=n1_i>n2_j?n1_i:n2_j;
        }
        else{
            double left=n1_i>n2_j?n1_i:n2_j;
            double right=n1_iplus1<n2_jplus1?n1_iplus1:n2_jplus1;
            median=(left+right)/2;
        }
        return median;
    }
};