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,能给讲一下吗?
|
|