题目描述
给定两个有序数组arr1和arr2，两个数组长度都为N，求两个数组中所有数的上中位数。
例如：
arr1 = {1,2,3,4};
arr2 = {3,4,5,6};
一共8个数则上中位数是第4个数，所以返回3。
arr1 = {0,1,2};
arr2 = {3,4,5};
一共6个数则上中位数是第3个数，所以返回2。
要求：时间复杂度O(logN)
程序代码
#include <iostream>
#include <vector>
using namespace std;
int getUpMedian(vector<int> arr1,vector<int> arr2){
int kth;
int k1=0,k2=0,k3=0;
int len1=arr1.size();
int len2=arr2.size();
int m;
if((len1+len2)%2==0)
kth=(len1+len2)/2;
else
kth=(len1+len2)/2+1;
while(k3!=kth){
if(k1<len1 && k2<len2){
if(arr1[k1]<arr2[k2]){
m=arr1[k1];
k1++;
}else{
m=arr2[k2];
k2++;
}
}else if(k1<len1 && k2>=len2){
m=arr1[k1];
k1++;
}else if(k1>=len1 && k2<len2){
m=arr2[k2];
k2++;
}else{
break;
}
k3++;
}
return m;
}
int main(){
vector<int> arr1;
arr1.push_back(2);
arr1.push_back(3);
arr1.push_back(4);
vector<int> arr2;
arr2.push_back(1);
arr2.push_back(5);
arr2.push_back(7);
cout<<getUpMedian(arr1,arr2)<<endl;
system("pause");
}