p****e
发帖数: 3548 | | p*****p
发帖数: 379 | 2 两个array大小一样就好写
或者就先merge起来
【在 p****e 的大作中提到】
: 会有简单点解法吗
: 面试出这个也太难了
| p****e
发帖数: 3548 | 3 Merge就不是O(log(m+n))了啊
【在 p*****p 的大作中提到】
: 两个array大小一样就好写
: 或者就先merge起来
| c***s
发帖数: 192 | 4 这个就是跟 kth of two sorted array一样的吗？
我刚被面到过，然后我告诉面试官我做过这道题，
他先让我讲了一下思路，然后写了特殊情况就过了。
折半比较就可以了啊。
【在 p****e 的大作中提到】
: 会有简单点解法吗
: 面试出这个也太难了
| l***4
发帖数: 1788 | 5 但是好写啊
如果会写O(log(m+n))的当然更好
【在 p****e 的大作中提到】
: Merge就不是O(log(m+n))了啊
| M******l
发帖数: 479 | 6 我一直搞不清楚折半比较的时候到底怎么算左边和右边的index，能给讲一下吗？
【在 c***s 的大作中提到】
: 这个就是跟 kth of two sorted array一样的吗？
: 我刚被面到过，然后我告诉面试官我做过这道题，
: 他先让我讲了一下思路，然后写了特殊情况就过了。
: 折半比较就可以了啊。
| c***s
发帖数: 192 | 7 如果找第k个小的值（数组从小到大排列）的话，
只要砍掉左边的就可以了，（右边的不用管）。
下面是从A数组的pa开始和B数组的pb开始中 找第k个最小的值。
int findMedian(int[] A, int pa, int B[], int pb, int k) {
int i, j = 0, n = k / 2, qa = A.length, qb = B.length;
if(k <= 3) {
int[] C = new int[(k + 1) * 2];
for(i = pa; i < qa && i <= pa + k; i++) C[j++] = A[i];
for(i = pb; i < qb && i <= pb + k; i++) C[j++] = B[i];
for(i = j; i < (k + 1) * 2; i++) C[i] = Integer.MAX_VALUE;
Arrays.sort(C);
return(C[k]);
}
int an = (pa + n >= qa - 1) ? qa - 1 : pa + n - 1;
int bn = (pb + n >= qb - 1) ? qb - 1 : pb + n - 1;
if(A[an] <= B[bn]) {
if(an == qa - 1) return(B[pb + k - (qa - pa)]);
return(findMedian(A, an, B, pb, k - (an - pa)));
}
if(bn == qb - 1) return(A[pa + k - (qb - pb)]);
return(findMedian(A, pa,B, qb, k - (bn - pb)));
}
【在 M******l 的大作中提到】
: 我一直搞不清楚折半比较的时候到底怎么算左边和右边的index，能给讲一下吗？
|
|
