谢谢回复,贴个JAVA版
public static int kthSmallest(int[] a, int [] b, int k){
if (a == null || b == null || a.length != b.length || k < 1 || k > a.
length + b.length)
throw new IllegalArgumentException("Invalid input");
if (k == 1)
return Math.min(a[0], b[0]);
if (k == a.length + b.length)
return Math.max(a[a.length-1], b[b.length-1]);
return kthSmallest(a, 0, b, 0, k);
}
private static int kthSmallest(int[] a, int aStart, int[] b, int bStart, int
k){
if (aStart >= a.length)
return b[bStart + k - 1];
if (bStart >= b.length)
return a[aStart + k - 1];
if (k == 1)
return Math.min(a[aStart], b[bStart]);
int kk = k/2;
int ak = Math.min(a.length-1, aStart + kk - 1), bk = Math.min(b.length-1
, bStart+kk - 1);
if (a[ak] <= b[bk])
return kthSmallest(a, ak+1, b, bStart, k - (ak-aStart+1));
else
return kthSmallest(a, aStart, b, bk+1, k - (bk-bStart+1));
}