LeetCoder_____Median of Two Sorted Arrays

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

Example 1:

nums1 = [1, 3]nums2 = [2]The median is 2.0
Example 2:
nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5
题意：
给出两个递增序列，求该两个递增序列合并后的中位数。
我的答案：
第一次做的时候，其实跟最佳答案很相近了。
对左边数组进行二分，找到二分位置的数字，然后用二分查找到右边数组查找这个数字的位置，然后判断两边元素个数是否相等。
最佳答案：
为了做这道题，我们需要去理解“中位数”. 在统计中, 在统计,中位数是用来将一组分成两个相等的长度子集,
其中一个子集每个元素总是大于等于另一个子集元素。如果我们理解的使用值划分,我们非常接近答案。
首先我让A根据一个随机位置i来分成两个部分。
      left_A             |        right_AA[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
因为有m个元素,所以有m + 1种(i = 0 ~ m)。我们知道:len(left_A)=i,len(right_A)= m - i。
注意:当i= 0,left_A是空的,当i= m,right_A是空的。
同样的方法，我让B根据一个随机位置j来分成两个部分
      left_B             |        right_BB[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
把left_A，left_B为一组,把right_A，right_B到另一组,我们的名字他们left_part，right_part:
      left_part          |        right_partA[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]
如果我们可以保证：
1) len(left_part) == len(right_part)2) max(left_part) <= min(right_part)
然后我们把所有元素以同样的长度分成两个部分进入left_part,right_part,然后其中一个part始终要大于等于另一个。
然后，median = (max(left_part) + min(right_part))/2.
为了确保这两个条件,我们只需要确保:
(1) i + j == m - i + n - j (or: m - i + n - j + 1)    if n >= m, we just need to set: i = 0 ~ m, j = (m + n + 1)/2 - i(2) B[j-1] <= A[i] and A[i-1] <= B[j]
细节不予多说了。
注意：part存在空集的情况。
代码：
class Solution {public:    double findMedianSortedArrays(vector<int> nums1, vector<int> nums2) {        int num = (nums1.size() + nums2.size() + 1) / 2;        if(nums1.size() > nums2.size()) nums1.swap(nums2);        if(nums1.size() == 0 && nums2.size() == 1) return nums2[0];        int num1 = nums1.size(),num2 = nums2.size();        int l = 0,r = nums1.size(),mid;        int mx,mi;        while(l<=r)        {            mid = (l+r)/2;            int rest = num - mid;            if(rest < 0){                r = mid - 1;continue;            }else if(rest > num2){                l = mid + 1;continue;            }            if(mid != 0 && rest == 0) mx = nums1[mid-1];            else if(mid == 0 && rest != 0) mx = nums2[rest-1];            else mx = max(nums1[mid-1],nums2[rest-1]);            if(mid != num1 && rest == num2) mi = nums1[mid];            else if(mid == num1 && rest != num2) mi = nums2[rest];            else mi = min(nums1[mid],nums2[rest]);            if(mx <= mi){                l = mid;                break ;            }            if(mid == 0){                l = mid + 1;            }else if(rest == 0){                r = mid - 1;            }else{                if(mx == nums1[mid-1])                    r = mid - 1;                else                    l = mid + 1;            }        }        if((num1+num2)%2){            return mx;        }else{            return (mi+mx)/2.0;        }    }};