网站做百度竞价引流费用多少钱外包接单平台

本题最好想的方法就是将两个数组排序，直接返回对应下标值，但是这样做的时间复杂度不满足要求，本题要求的时间复杂度为logn，因此采用二分法。

对于两个排序数组，若是两个数组的中位数相等，则两个数组的上中位数也是该数。设置两个数组的左有边界下标分别为 l1=0,r1=n-1,l2=0,r2=n-1; n是数组的长度。中位数的下标为mid1=mid2=(r1+l1)/2。分为三种情况：

• arr1[mid1]==arr2[mid2]，则两个数组的上中位数为arr1[mid1]；
• arr1[mid1]>arr2[mid2]，则分为两种情况讨论：①若是范围内的数据个数是偶数，即flag=(l1+r1)%2为0，则r1=mid1;l2=mid2+1；②若是范围内的数据个数是偶数，即flag=(l1+r1)%2不为0，则r1=mid1;l2=mid2；即将查找范围缩小至原范围的一半。
• arr1[mid1]<arr2[mid2]，则分为两种情况讨论：①同上，falg为0，则l1=mid1+1;r2=mid2 ② flag不为0，则l1=mid1;r2=mid2；查找范围缩小至一半。

最后当条件不满足l1<r1时，则返回min(arr1[l1],arr2[l2]);

最后结合代码理解：

class Solution {
public:/*** find median in two sorted array* @param arr1 int整型vector the array1* @param arr2 int整型vector the array2* @return int整型*/int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {// write code hereint n=arr1.size();if(n==1) return min(arr1[0],arr2[0]);int l1=0,r1=n-1,l2=0,r2=n-1;int flag=(r1-l1+1)%2; //flag为0，则个数是偶数个while(l1<r1){int mid1=(l1+r1)/2;int mid2=(l2+r2)/2;flag=(r1-l1+1)%2;if(arr1[mid1]==arr2[mid2]) return arr1[mid1];else if(arr1[mid1]>arr2[mid2]){if(flag){   //个数为奇数r1=mid1;l2=mid2;}else{r1=mid1;l2=mid2+1;}}else{if(flag){    //个数为奇数l1=mid1;r2=mid2;}else{l1=mid1+1;r2=mid2;}}}return min(arr1[l1],arr2[l2]);}
};