Redian新闻
>
问道小学题:两等长有序数组,求第k个数
avatar
问道小学题:两等长有序数组,求第k个数# JobHunting - 待字闺中
n*r
1
我目前的做法是去A,B数组的中位数进行比较,然后根据最大的中位数左边的元素个数
和k进行比较来丢弃A或B的一端数据,递归的缩小范围。
还有其他更好的更简洁的解法没有?
avatar
n*r
2
是不是可以有logK的解法?
avatar
G*e
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的解法?
avatar
n*r
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));
}
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。