WIN 8 Setup 有什么建议？# Hardware - 计算机硬件
g*y
1 楼
A/G都问的一道：Find kth smallest number in union of two sorted arrays
好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
public int get(int[] a, int[] b, int k) {
int lower = Math.max(0, k-b.length-1);
int upper = Math.min(a.length-1, k-1);
int i = (lower + upper) / 2;
return get(a, b, k, lower, i, upper);
}
private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
int j = k - i - 2;
if (j < 0) return Math.min(a[i], b[0]);
if (a[i] == b[j]) {
return a[i];
}
else if (a[i] < b[j]) {
if (i == upper) return b[j];
return get(a, b, k, i, (i+1+upper)/2, upper);
}
else { // a[i] > b[j]
if (i == lower) return a[i];
if (i == lower+1) return a[lower]>=b[j+1]? a[lower] : Math.min(a[i], b[j+1]);
return get(a, b, k, lower, (i-1+lower)/2, i);
}
}
好象网上公认的最佳解是logM+logN。我写完code, 感觉log(min(M,N))就够了，如果错了，请指正。
思路是用的ihasleetcode的：i+j=k, 既然k是固定的，那我只需要找出i, 这个i我当然可以挑一个短的序列找。以下code是找针对数组a的指针i, 要是b是短的，稍改一下程序就行。
public int get(int[] a, int[] b, int k) {
int lower = Math.max(0, k-b.length-1);
int upper = Math.min(a.length-1, k-1);
int i = (lower + upper) / 2;
return get(a, b, k, lower, i, upper);
}
private int get(int[] a, int[] b, int k, int lower, int i, int upper) {
int j = k - i - 2;
if (j < 0) return Math.min(a[i], b[0]);
if (a[i] == b[j]) {
return a[i];
}
else if (a[i] < b[j]) {
if (i == upper) return b[j];
return get(a, b, k, i, (i+1+upper)/2, upper);
}
else { // a[i] > b[j]
if (i == lower) return a[i];
if (i == lower+1) return a[lower]>=b[j+1]? a[lower] : Math.min(a[i], b[j+1]);
return get(a, b, k, lower, (i-1+lower)/2, i);
}
}
