n****r
发帖数: 120 | 1 我目前的做法是去A，B数组的中位数进行比较，然后根据最大的中位数左边的元素个数
和k进行比较来丢弃A或B的一端数据，递归的缩小范围。
还有其他更好的更简洁的解法没有？ | n****r
发帖数: 120 | | G******e
发帖数: 229 | 3 Yes. Use the method of binary search: compare the k/2-th smallest elements
in both list A[k/2] and B[k/2]. If A[k/2] <= B[k/2], throw away A[1] through
A[k/2] (and vice versa). Now recurse on the two new list with parameter k/2.
【在 n****r 的大作中提到】
: 是不是可以有logK的解法？
| n****r
发帖数: 120 | 4 谢谢回复，贴个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));
} |
|
