因为有序,所以可以用类似二分排除的策略,时间复杂度为log(min(m,n))。
typedef vector<int>::iterator itr;
int findKthInTwoArr(itr A, int m, itr B, int n, int k){
if(m>n){
return findKthInTwoArr(B,n,A,m,k);
}
if(m==0){
return *(B+k-1);
}
if(k==1){
return min(*A,*B);
}
int a=min(k/2,m);
int b=k-a;
if(*(A+a-1)<*(B+b-1)){
return findKthInTwoArr(A+a,m-a,B,n,k-a);
}else if(*(B+b-1)<*(A+a-1)){
return findKthInTwoArr(A,m,B+b,n-b,k-b);
}else{
return *(A+a-1);
}
}