商务网站建设实训报告总结_服务企业是什么_公司网站设计制作_站长工具四叶草

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

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

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

分析：题目要求用 O(log(m+n))的算法，因此首先想到二分。但是这道题二分的不是数组，而是每次删去的数的数量。不妨设要找两个数组中第k大的值，同时a、b两个数组的长度均为k*2。

每次在a、b两个数组中，比较第k/2个元素的大小。此时设a[k/2]<b[k/2]。对于a[k/2]来说，因为它是小于b[k/2]的，因此它一定是排在两个数组的第k个元素之前，也就是说，对于a[0]-a[k/2]这些元素，它们一定都是在第k个元素的前面，所以下一次查找时，可以不用考虑这些元素，同时下次查找的数变成k/2/2。就这样每次去掉一半，直到k=1，取两个数组中第一个较小的值即可。

再来考虑边界条件。有可能a数组很小（b数组很小的情况同理），它的长度可能不足以取k/2。当a数组走到右边界之外，直接取b数组中对应剩下的第k’个元素即可。

int findans(int* nums1, int nums1Size, int* nums2, int nums2Size,int t)
{int l1=0,l2=0,r1=nums1Size,r2=nums2Size,m1,m2;
//    db1(t);int ans=0,tt;while(t>=1)//每次循环减去t的一半数字，或者某一个数组的数字已经不够减了，直接选另一个数组的当前第t个数字{if(t==1){
//            db2(nums1[l1],nums2[l2]);if(l1==r1)return nums2[l2];else if(l2==r2)return nums1[l1];return fmin(nums1[l1],nums2[l2]);}tt=t/2;if(r1-l1>=tt)m1=l1+tt-1;else if(l1!=r1)m1=r1-1;else m1=r1;if(r2-l2>=tt)m2=l2+tt-1;else if(l2!=r2)m2=r2-1;else m2=r2;//        db2(m1,m2);db5(l1,r1,l2,r2,tt);if(m1==r1){ans=nums2[l2+t-1];
//            db2('a',ans);return ans;}else if(m2==r2){ans=nums1[l1+t-1];
//            db2('b',ans);return ans;}if(nums1[m1]<=nums2[m2])t-=m1-l1+1,l1=m1+1;else t-=m2-l2+1,l2=m2+1;tt=t/2;
//        db1(t);db5(l1,r1,l2,r2,tt);printf("\n");}
//    db1(ans);return ans;
}double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {//边界条件：一个数组长度为0时，或者它当前的长度不足删除的时候int ans1,ans2;ans2=ans1=findans(nums1,nums1Size,nums2,nums2Size,(nums1Size+nums2Size+1)/2);if((nums1Size+nums2Size+1)&1)ans2=findans(nums1,nums1Size,nums2,nums2Size,(nums1Size+nums2Size+1)/2+1);
//    db2(ans1,ans2);return 1.0*(ans1+ans2)/2.0;
}