试着写了一下，好像可以，没有仔细测试。
public class FindKthFromTwoArray{
public static void main(String[] args)
{
int[] a = {2,4,6,7,8,10,19,20,24,98};
int[] b = {2,5,15,18,27,34,56,67,100,140};
// int[] a = {2,4,19,29,39,49,59};
// int[] b = {1,5,6,7,12,29,30,33,45,67,78};
// int[] a = {2};
// int[] b = {1};
int k = 16;
int result = FindKthFromTwoArray.findKth(a,b,k);
System.out.println("The kth number is: " + result);
}
public static int findKth(int[] a, int[] b, int k){
return findKth(a,0,b,0,k);
}
private static int findKth(int[] a, int aoffset, int[] b, int boffset,
int k){
assert a.length + b.length >= k+1;
int sa,sb;
if (k == 0) return a[aoffset]< b[boffset]? a[aoffset]:b[boffset];
if (k%2 == 0){
sa= k/2; sb = k/2-1;
}
else {
sa= k/2; sb = k/2;
}
int amid = sa + aoffset;
int bmid = sb + boffset;
if (amid > a.length-2)
return linearSearch(a,aoffset,b,boffset,k);
if (bmid > b.length-2)
return linearSearch(a,aoffset,b,boffset,k);
if (a[amid] < b[bmid])
return findKth(a,amid+1,b,boffset,k-sa-1);
else
return findKth(a,aoffset,b,bmid+1,k-sb-1);
}
public static int linearSearch(int[] a, int aStart, int[] b, int bStart,
int k){
int count = 0;
int i=aStart,j=bStart;
while(count < k){
if (i == a.length-1 && j == b.length-1)
return a[i]> b[j]? a[i]:b[j];
if (i == a.length-1){
j++;
if (b[j] >= a[i])
return b[k-a.length];
}
else if (j == b.length-1){
i++;
if (a[i] >= b[j])
return a[k-b.length];
}
else{
if(a[i] < b[j])
i++;
else
j++;
}
count++;
}
return a[i]< b[j]? a[i]:b[j];
}
}
