c*******r
发帖数: 309 | 1 这个binary search是怎么做啊?
我只想到merge再直接找第k个 | s******n
发帖数: 226 | 2 假设第一个数组有L个元素在前k个元素里（两个数组） 然后binary L | p*****2
发帖数: 21240 | 3 array: A, B
index: i, j
你需要找到
1. i+j+2=k
2. B[j]
3. A[i]
return max(A[i], B[j])
at the beginning
i=0
j=k-2
然后binary search。 | s****j
发帖数: 67 | 4 int a[maxn],b[maxn];
int find(int aleft,int aright,int bleft,int bright,int k) {
if ((aright-aleft+1)+(bright-bleft+1)
cout<<"error"<
return 0;
}
if (aleft>aright)
return b[bleft+k-1];
if (bleft>bright)
return a[aleft+k-1];
int amid=(aleft+aright)>>1;
int bmid=(bleft+bright)>>1;
if (a[amid]<=b[bmid])
if (k<=(amid-aleft)+(bmid-bleft)+1)
return find(aleft,aright,bleft,bmid-1,k);
else
return find(amid+1,aright,bleft,bright,k-(amid-aleft+1));
else
if (k<=(amid-aleft)+(bmid-bleft)+1)
return find(aleft,amid-1,bleft,bright,k);
else
return find(aleft,aright,bmid+1,bright,k-(bmid-bleft+1));
}
【在 c*******r 的大作中提到】
: 这个binary search是怎么做啊?
: 我只想到merge再直接找第k个
| k****n
发帖数: 369 | 5 最简单的办法是坐n-way merge sort
【在 c*******r 的大作中提到】
: 这个binary search是怎么做啊?
: 我只想到merge再直接找第k个
|
|
