问道小学题：两等长有序数组，求第k个数# JobHunting - 待字闺中
n*r
1 楼
我目前的做法是去A，B数组的中位数进行比较，然后根据最大的中位数左边的元素个数
和k进行比较来丢弃A或B的一端数据，递归的缩小范围。
还有其他更好的更简洁的解法没有？
和k进行比较来丢弃A或B的一端数据，递归的缩小范围。
还有其他更好的更简洁的解法没有？
n*r
2 楼
是不是可以有logK的解法？
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的解法？
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
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));
}
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));
}
相关阅读
像我这种情况，找工作需要考虑办绿卡的问题么?菜鸟问一个resume的问题 跪求回答啊~B家面筋请问H1B可以换工作地点吗？问surrounded region求多伦多IT公司内推为什么回复HR邮件后就没信了工作进退两难，咨询下意见在garage等换油，修车这个职业其实不错linkedin上主动联系人的startup的CXO都是真的么？What is the cool down period for FLAG companies?做会计电算化5年了，最近拿到一个offer，跳不跳？刚被layoff了, 有没有靠谱点的律师可以咨询H1B的事情吗急问：老总面试都会问什么提供yahoo内推，team在扩招！非java码工请教啥是“轮子”？一个国内同学的阿里现状微软裁员是不是意味着马工市场上突然多了一堆人竞争问一个time series forecasting的问题遇到这种情况要怎么回复比较好