问道小学题：两等长有序数组，求第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));
}
相关阅读
如何在LinkedIn上找工作？请问大家背景check都调查啥啊？被DP郁闷到了...onsite 穿什么？OPT问题求助！大家跳槽一般要求工资比原先的高多少呀？6 years limits of H1bbloomberg 电话面试询问how to negotiate请问自己可以办H1B么？这个时侯还有没找到summer intern的CS phd么？请教一个关于猎头的问题面试时怎么称呼对方?who has facebook recruiters' contact info? I really appreciate it!刚据了一个公司,又开始了零offer的状态。好累。。。找了半年工作，好不容易拿了个口头的offer 就怕黄了啊A家面经, offer, 请教NegotiationOPT三个月快到了，想找导师挂一下volunteer, 要办啥手续有些recruiter的态度实在太恶劣去实习要换I-20? 换成什么样的啊？