两个递增数组中位数

预处理：如果有一个数组为空，那么根据奇偶两种情况返回解。

• 输入如果是奇数长度数组，返回排length/2位置即可，如果是偶数长度数组，返回length/2和length/2+1两个数的平均数即可。

（1）求两个数组各自的前k/2个数的最大值，哪个大就保留哪个数组的前k/2个，然后抛弃另一个数组的前k/2个数。
（2）如果其中一个数组长度小于等于k/2那么就尝试抛弃另一个数组前k/2个数，如果另一个数组前k/2个数的最大值大于该数组，那就抛弃失败只能抛弃该数组所有成员（该数组长度为kk），然后抛弃另一个数组前k-kk个成员。
（3）如果两个数组长度都等于k/2，那么就返回两个数组最大的那个值
（4）如果都小于k/2，那么无解。

#include<bits/stdc++.h>
using namespace std;
// k 以1为array开始，从小到大取，计算的时候要注意
double findK(vector<int>& num1, vector<int>& num2,int l1,int r1,int l2,int r2,int k){
    if(k==1){
        return num1[l1]>num2[l2]?num2[l2]:num1[l1];
    }
    if(k/2==r2-l2+1==r1-l1+1){
        return num1[r1]>num2[r2]?num1[r1]:num2[r2];
    }
    if((k/2)>=r2-l2+1){
        if(num2[r2]>=num1[l1+k/2-1]){
            return findK(num1,num2,l1+k/2,r1,l2,r2,k-k/2);
        }
        else{
            return double(num1[l1+k-(r2-l2+1)-1]);
        }
    }
    if((k/2)>=r1-l1+1){
        if(num1[r1]>=num2[l2+k/2-1]){
            return findK(num1,num2,l1,r1,l2+k/2,r2,k-k/2);
        }
        else{
            return double(num2[l2+k-(r1-l1+1)-1]);
        }
    }
    if(num1[l1+k/2-1]>=num2[l2+k/2-1]){
        return findK(num1,num2,l1,r1,l2+k/2,r2,k-k/2);
    }
    else{
        return findK(num1,num2,l1+k/2,r1,l2,r2,k-k/2);
    }
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if(nums1.size()==0){
        if(nums2.size()&1){
            return nums2[(nums2.size()-1)/2];
        }
        else{
            return (nums2[(nums2.size()-1)/2]+nums2[(nums2.size()-1)/2+1])/2.0;
        }
    }
    if(nums2.size()==0){
        if(nums1.size()&1){
            return nums1[(nums1.size()-1)/2];
        }
        else{
             return (nums1[(nums1.size()-1)/2]+nums1[(nums1.size()-1)/2+1])/2.0;
        }
    }
    int l1=0;
    int r1=nums1.size()-1;
    int l2=0;
    int r2=nums2.size()-1;
    if((nums1.size()+nums2.size())&1){
        return findK(nums1,nums2,l1,r1,l2,r2,(nums1.size()+nums2.size())/2+1);
    }
    else{
        return (findK(nums1,nums2,l1,r1,l2,r2,(nums1.size()+nums2.size())/2)+findK(nums1,nums2,l1,r1,l2,r2,(nums1.size()+nums2.size())/2+1))/2.0;
    }
}
int main(){
    vector<int>num1{1};
    vector<int>num2{2};
    double res=findMedianSortedArrays(num1,num2);
    cout<<res;
}