[记录]letcode每日一刷:寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 ，时间复杂度为 O(log (m+n)) 的算法

输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
解释： 合并数组 = [1,2,3] ，中位数 2
复制代码

因为数组长度可能是偶数，所以中位数可能是中间两个数的平均数，返回的数据也就可能是小数。所以数据类型为double，本文使用java语言实现

思考

此问题在letcode标注的难度是困难，究其原因就在于O(log (m+n))的时间复杂度

第一反应相信大家都是一样的，直接合并两个有序数组，然后取中间的值，或者中间两个值的平均数，但是显然是打不到时间复杂度的要求。

涉及到log级别的复杂度，很容易想到跟二分法相关，因为这样才是log级别的时间复杂度，转换下思路，一个有序数组的中位数，其实可以理解为是寻找第K大的数字位置

而且是两个有序的数组，所以只要找个每个数组对应的中位数k1,k2，再次进行比较，即可获取到最终的结果，举个例子

假如数组m的长度为5,n的长度为4，那么总数组中位数的位置是第五个k=5，那么5/2=2,找到每个数组的第二个数，进行比较，如果m[1]>n[1]，那么直接抛弃n的前面2个数字，同时k=5-2=3

第二轮k=3,3/2=1,找到每个数组的第1个数(注意，这里n应该是第三个数，因为前面2个已经去掉了)，以此类推，最终K=1，那么也就是说，还需要找到最后一个最小的数字则即可中位数，那么，直接比较m[i],n[j]的大小即可

上代码

@Test
public void Test(int[] nums1, int[] nums2){
    //因为是第K小的数，所以对应到数组里面的索引的话，需要+1
    int left = (nums1.length+nums2.length+1)/2;
    int right = (nums1.length+nums2.length+2)/2;
    //这里分偶数和奇数，所以计算两次求平均数，奇数的话，会求取两次相同的值
    return (getResult(nums1,0,nums1.length-1,nums2,0,nums2.length-1,left)+
    getResult(nums1,0,nums1.length-1,nums2,0,nums2.length-1,right))*0.5;
}
public int getResult(int[]num1,int start1,int end1,int[] num2,int start2,int end2,int k){
   //算出两个数组的长度
   int len1 = end1-start1+1;
   int len2 = end2-start2+1;
   //这里为了避免各种判断，直接通过判断来保证num1数组的最短的，
   if (len1>len2) return getResult(num2,start2,end2,num1,start1,end1,k);
   //出口1:如果其中一个数组被排查完了，那么直接去剩下一个数组第k-1个位置的数组即可
   if (len1==0) return num2[start2+k-1];
   //出口2，如果k=1了，那么直接，比较两个数组的第一个数字即可
   if (k==1) return Math.min(num1[start1],num2[start2]);
   //每次取k/2+数组的起始位置进行
   int i = start1+Math.min(len1,k/2)-1;
   int j = start2+Math.min(len2,k/2)-1;
   //数值进行比较，不断递归，到上面的出口为止。
   if (num1[i]>num2[j]){
       return getResult(num1,start1,end1,num2,j+1,end2,k-(j-start2+1));
   }else{
       return getResult(num1,i+1,end1,num2,start2,end2,k-(i-start1+1));
   }

}
复制代码