Leetcode-04 寻找两个有序数组的中位数

令人头秃的困难题
仅写我的部分理解，详见学习题解链接。

1、变量解释
LMax：切割点左侧最大元素
RMin：切割点右侧最小元素
cut:中位数的切割点
eg：[1,2,3] LMax=RMin=2   [1,2] LMax=1 RMin=2

2、中位数
中位数切点满足的条件有：(LMax1<=RMin2)&&(LMax2<=RMin1)&&(cut1 cut2==len1 len2)

其中cut1 cut2==len1 len2(最终的切点下标是len1 len2，实际对应位置是len1 len2 1),因为虚拟加后的数组长度和为2len1 2len2 2。
结果为result=(max(LMax1,LMax2) min(RMin1,RMin2))/2.0

3、虚拟数组
由于求中位数存在奇数偶数的问题，我们虚拟的在数字之间加上一个#.
2n 1永远都是奇数，eg：1 2 3 变成 #1#2#3#
这样就可以保证下式成立
LMaxi = (Ci-1)/2 位置上的元素
RMini = Ci/2 位置上的元素
在实际的计算中，没有人真的在数字之间加入#,只是在计算时先乘以2，按照下标取数时再除以2.

4、如果一个数组完全小于等于另一个？
C1 = 0 —— 数组1整体都在右边了，所以都比中值大，中值在数组2中，简单的说就是数组1割后的左边是空了，所以我们可以假定LMax1 = INT_MIN
C1 =2*len1 —— 数组1整体都在左边了，数组1割后的右边是空了，中值在数组2中，在数组1中你找不到元素能满足(LMax2<=RMin1)，所以我们可以假定RMin1= INT_MAX。
C2 = 0 —— 数组2整体在右边了，数组2割后的左边是空了，所以我们可以假定LMax2 = INT_MIN.
C2 = 2*len2 —— 数组2整体在左边了，数组2割后的右边是空了，为了让LMax1 < RMin2 恒成立，我们可以假定RMin2 =INT_MAX,事实上，仅当len1=len2时可能触发这种结果。

#define debug(x) cout<<#x<<x<<endl;#define max(a,b) (((a) > (b)) ? (a) : (b))#define min(a,b) (((a) < (b)) ? (a) : (b))class Solution {public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {        int len1=nums1.size();        int len2=nums2.size();        if(len1>len2)        {            return findMedianSortedArrays(nums2,nums1);        }        int LMax1,LMax2,RMin1,RMin2,cut1,cut2,lf=0,rt=2*len1;        while(lf<=rt)        {            cut1=(lf rt)/2;            cut2=len1 len2-cut1;            LMax1=(cut1==0)?INT_MIN:nums1[(cut1-1)/2];            LMax2=(cut2==0)?INT_MIN:nums2[(cut2-1)/2];            RMin1=(cut1==2*len1)?INT_MAX:nums1[cut1/2];            RMin2=(cut2==2*len2)?INT_MAX:nums2[cut2/2];            if(LMax1>RMin2)                rt=cut1-1;            else if(LMax2>RMin1)                lf=cut1 1;            else               break;        }        return (max(LMax1,LMax2) min(RMin1,RMin2))/2.0;    }};

来源：https://www.icode9.com/content-4-658451.html