LeetCode 第四题 Median of Two Sorted Arrays（计算两个有序数组的中位数）

  这题要求的时间复杂度为$O(log(m+n))$，这一点感觉挺难想的，我打算是用递归将一个数组分割然后插入到另一个数组中，不过调了很久都没过，题解中的解法很巧妙，而且可以用在找两个有序数组中第$k_{th}$元素。

  下面看一下中位数的作用：

将一个集合分成连个长度相等的子集合，其中一个子集合中的元素全部大于另一个子集合中的元素

  随机将一个长度为$m$的数组分成两份，我们一共有$m+1$种分法。$i=0\to m$

left_A	right_A
$A[0],A[1],…..,A[i-1]$	$A[i],A[i+1],…..,A[m-1]$

其中有$len(left_A)=i，len(right_A)=m-i$，当$i=0$的时候，左边部分为空，当$i=m$的时候，右半部分为空。
  同理,若我们将数组$B$也随机分割:

left_B	right_B
$B[0],B[1],…..,B[j-1]$	$B[j],B[j+1],…..,B[n-1]$

  然后我们将两个数组的左半边和右半边进行合并

left_part	right_part
$A[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]$

这时，如果满足条件：

• $len(left_part)=len(right_part)$
• $max(left_part)\leq min(right_part)$

那么这时候，我们已经将$\{A,B\}$分成了长度相等的两个集合，而且有一个集合中的元素总是大于另一个集合中的元素，这样我们就找到了中位数了，即$median = \frac{max(left\_part)+min(right\_part）}{2}$
为了满足上面两个条件，我们只需要满足:

• $i+j = \frac {(m+n+1)}{2}$，即$j=\frac {(m+n+1)}{2}-i$
• $A[i-1]\leq B[j]$ and $B[j-1]\leq A[i]$

  这里我们假设有$n>m$，由于$0\leq i \leq m$，那么$j$就一定为一个非负数。(这里，要是我们将上面的条件改为$i+j=k$，那么就可以查找$k_{th}$的数)
所以我们只需要二分查找$i$的位置，即可得到答案。步骤如下所示：

• 设置左边界$L=0$，右边界$R=m$，从区间$[L,R]$开始查找
• 让$i=\frac {L+R}{2}$，$j=\frac {(m+n+1)}{2}-i$
• 现在我们已经满足$len(left_part)=len(right_part)$，只需满足第二个条件即可。
  • 如果满足$A[i-1]\leq B[j]$ and $B[j-1]\leq A[i]$，那么我们已经得到了解，退出二分查找即可
  • 如果有$A[i-1] > B[j]$ ，说明我们的$A[i-1]$太大了，所以我们需要减小$i$,由于减小$i$时，$j$会增大，所以能找到我们要的解。而如果我们增大$i$，同时$j$会变小，所以不能得到解，所以此时，我们应该让$R = i-1$,，然后继续查找
  • 如果有$B[j-1] > A[i]$ ，说明我们的$A[i]$太小了，所以我们需要增大$i$,理由同上，所以此时，我们应该让$L = i+1$，然后继续查找

最后当$i$找到的时候，分奇偶两种情况

• $max(A[i-1],B[j-1])$，当$m+n$为奇数
• $\frac {max(A[i-1],B[j-1])+min(A[i],B[j])} {2}$，当$m+n$为偶数

  考虑到当$i=0,i=m,j=0,j=n$时，$A[i-1],B[j-1],A[i],B[j]$可能不存在，由于我们只是要判断是否满足条件，所以我们当元素不存在时，就不用进行判断了。也就是说，

• $(j=0$ || $i=m$ || $B[j-1] \leq A[i]$ && $A[i-1] \leq B[j])$
• $(j>0$ && $i A[i]$)$
• $(i>0$ && $j B[j]$)$

  代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m  = nums1.size();
        int n = nums2.size();
        
        //我们需要保持 n>m
        if(m>n)
        {
            swap(nums1,nums2);
            swap(m,n);
        }
        
        //二分法查找i  
        int L = 0,R = m;
        int len = (m+n+1)/2;
        while(L<=R)
        {
            int i = (L + R)/2;
            int j = len-i;
            //i太小
            if(j>0&&i<R&&nums2[j-1]>nums1[i])
            {
                L = i+1;
            }
            //i太大
            else if(i>0&&j<n&&nums1[i-1]>nums2[j])
            {
                R = i-1;
            }
            //满足两个条件，我们得到了解
            else
            {
                //首先求左边的最大值
                int maxleft = 0;
                if(i==0) {maxleft = nums2[j-1];}
                else if(j==0){maxleft = nums1[i-1];}
                else{maxleft  = max(nums1[i-1],nums2[j-1]);}
                //判断是否为奇数
                if((m+n)%2==1) return maxleft;
                
                int minright = 0;
                if(i == m) minright = nums2[j];
                else if(j == n) minright = nums1[i];
                else{minright = min(nums1[i],nums2[j]);}
                
                return (maxleft+minright)/2.0;
            }
        }
        
        return 0.0;
    }
};