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

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

转化成求两个有序数组的第k大，当x+y=k,arr1[x-1]<arr2[k-x],arr[x]>arr2[y-1] , max(arr1[x-1].arr2[y-1])为第k大

感觉写的好乱啊，QAQ，改天理清思路重新写下。

 1 class Solution {
 2 public:
 3     double findkth_num(vector<int>& nums1,vector<int>& nums2,int k){
 4         int l = max(0,k-(int)nums2.size());
 5         int r = min(k,(int)nums1.size());
 6       //  cout<<l<<r<<endl;
 7 
 8 
 9         //l=0,r=nums1.size();
10         for(int i=0;i<100;++i){
11             int mid=(l+r)/2;/*
12             if(k-mid-1>=(int)nums2.size())l=mid;
13             else if(k-mid-1<0){
14                 r=mid;
15             }
16             else*/
17             if(k-mid-1<0)continue;
18             if(nums2[k-mid-1]>nums1[mid])l=mid;
19             else r=mid;
20         }
21         auto Lmax=INT_MIN,Rmax=INT_MIN;
22         if(r-1>=0)Lmax=nums1[r-1];
23         if(k-r-1>=0)Rmax=nums2[k-r-1];
24         cout<<Lmax<<' '<<Rmax<<endl;
25         return max(Lmax,Rmax);
26     }
27     double get(vector<int>&nums2){
28                int siz = nums2.size();
29                if(siz%2==0)return (nums2[siz/2-1]+nums2[siz/2])/2.0;
30                return nums2[siz/2];
31               // if(nums2.size()%2==0)return nums2[nums2]
32     }
33     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
34            if(!((int)nums1.size()) )return get(nums2);
35            if(!((int)nums2.size()) )return get(nums1);
36            if(nums1.size()+nums2.size()==2)return (nums1[0]+nums2[0])/2.0;
37            int k=nums1.size()+nums2.size();
38            if((k&1))return findkth_num(nums1,nums2,k/2+1);
39            return (findkth_num(nums1,nums2,k/2)+findkth_num(nums1,nums2,k/2+1))/2.0;
40     }
41 };