Given two sorted list, find the k smallest number (binary search)# JobHunting - 待字闺中
c*r
1 楼
这个binary search是怎么做啊?
我只想到merge再直接找第k个
我只想到merge再直接找第k个
s*n
2 楼
假设第一个数组有L个元素在前k个元素里（两个数组） 然后binary L
s*j
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)
}
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个
int find(int aleft,int aright,int bleft,int bright,int k) {
if ((aright-aleft+1)+(bright-bleft+1)
}
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
5 楼
最简单的办法是坐n-way merge sort
【在 c*******r 的大作中提到】
: 这个binary search是怎么做啊?
: 我只想到merge再直接找第k个
【在 c*******r 的大作中提到】
: 这个binary search是怎么做啊?
: 我只想到merge再直接找第k个
相关阅读
为啥有的公司职位在网上挂了一年左右还没招到人？Uber 现在值得去吗？芝加哥内推Technical Manager/Technical Lead Position and Ot已经收满了- Software Engineer InternPython 开发岗位Chicago at Trading Firm安身立命的法宝，就是自己足够的强大！Google qualitative UX researcher 求捞问个Intel offer级别是不是被lowball了人生输家破釜沉舟求转型建议请大家帮忙看看这non-competition究竟啥意思。。。洗脚哥 请问 PA 火车道附近的居民怎么活过来的？ (转载)大陆来的留学生以后很难进入美国高科技公司了 (转载)一线E5还是二线M1?问大牛们这个startup offer值不值得去phone interview 技巧问题急问亚麻的OA 能推迟吗？多谢endorsement的作用有多大？没人恭喜zoom的同志们吗华州AA通过之后 STEM工作及学校录取再次提上议程 其他AA措施陆 (转载)跳槽的话原公司的title、级别应该无所谓吧？