k*w
2 楼
群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
版主的版友请楼下表达你们的支持！顶此楼进十大！
琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
版主的版友请楼下表达你们的支持！顶此楼进十大！
A*C
3 楼
贝勒医学院教授、“千人计划”秦钧在中国讲“中国特色社会主义新时代蛋白组学”，
不怕被联邦调查局叫去喝咖啡？
不怕被联邦调查局叫去喝咖啡？
c*9
4 楼
大小为K的min heap去扫整个数组，O（MN）*logk，第一时间只有这个想法
k*w
5 楼
啥不说，谢谢！
r*n
6 楼
sarcasm 懂不懂？
w*x
7 楼
这题太难了, 别看了, 不会考
y*0
8 楼
支持，太支持了
w*x
9 楼
有种解法是基于数值的2分, 实现起来也很绕. 原题是给两个排序的数组 A, B. 如果a
->A, b->B, 求第k大的a + b, 可以化成杨氏矩阵求解, 没记错因该是Google的题, 我
见过最难的题之一
->A, b->B, 求第k大的a + b, 可以化成杨氏矩阵求解, 没记错因该是Google的题, 我
见过最难的题之一
L*n
10 楼
支持
D*g
11 楼
maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
一个数字以及每个数字对应的行号。
然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
out，change root value to some MAX value, then heapify.
如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
，直到找到为止。
这么看来用balanced search tree应该更合适，klog(m)的复杂度。
【在 f*********i 的大作中提到】
: 求递增二纬数组，就是排列按行递增，按列也递增的数组（m*n）的第k大的数。
: 请问有没有比较好的解法。
一个数字以及每个数字对应的行号。
然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
out，change root value to some MAX value, then heapify.
如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
，直到找到为止。
这么看来用balanced search tree应该更合适，klog(m)的复杂度。
【在 f*********i 的大作中提到】
: 求递增二纬数组，就是排列按行递增，按列也递增的数组（m*n）的第k大的数。
: 请问有没有比较好的解法。
r*u
12 楼
support
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
l*c
13 楼
binary search from (0,0), to (m, n)
log(m + n)
amazon asked me this question during the phone interview
【在 f*********i 的大作中提到】
: 求递增二纬数组，就是排列按行递增，按列也递增的数组（m*n）的第k大的数。
: 请问有没有比较好的解法。
log(m + n)
amazon asked me this question during the phone interview
【在 f*********i 的大作中提到】
: 求递增二纬数组，就是排列按行递增，按列也递增的数组（m*n）的第k大的数。
: 请问有没有比较好的解法。
l*e
14 楼
支持，好人一生平安
g*x
15 楼
Is it to find the K-th number, or to find "K"?
【在 l******c 的大作中提到】
: binary search from (0,0), to (m, n)
: log(m + n)
: amazon asked me this question during the phone interview
【在 l******c 的大作中提到】
: binary search from (0,0), to (m, n)
: log(m + n)
: amazon asked me this question during the phone interview
N*0
16 楼
support!
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
l*8
17 楼
find the K-th number
【在 g**x 的大作中提到】
: Is it to find the K-th number, or to find "K"?
【在 g**x 的大作中提到】
: Is it to find the K-th number, or to find "K"?
k*1
18 楼
支持！
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
g*x
19 楼
I am confused by what "lclclclc" said.
It is Ok to use binary search to find "k".
It seems not right to use binary search to get K-th number.
【在 l*********8 的大作中提到】
: find the K-th number
It is Ok to use binary search to find "k".
It seems not right to use binary search to get K-th number.
【在 l*********8 的大作中提到】
: find the K-th number
g*n
20 楼
没降级的eb2，在这里支持版主们！
★ 发自iPhone App: ChineseWeb 8.7
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
★ 发自iPhone App: ChineseWeb 8.7
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
g*x
21 楼
K-way merge is good. But it doesn't gain the benefits of the condition that
each column is also in increasing order.
How about this:
Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
1)Delete the root of the heap;
2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
pick up [i+1,j] and [i,j+1]).
3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
The time complexity is K Log(K) (For each loop, heap size increase at most,
so the heap size is K). It would be faster when K<
run
【在 D********g 的大作中提到】
: maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
: 一个数字以及每个数字对应的行号。
: 然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
: out，change root value to some MAX value, then heapify.
: 如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
: 要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
: ，直到找到为止。
: 这么看来用balanced search tree应该更合适，klog(m)的复杂度。
each column is also in increasing order.
How about this:
Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
1)Delete the root of the heap;
2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
pick up [i+1,j] and [i,j+1]).
3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
The time complexity is K Log(K) (For each loop, heap size increase at most,
so the heap size is K). It would be faster when K<
run
【在 D********g 的大作中提到】
: maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
: 一个数字以及每个数字对应的行号。
: 然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
: out，change root value to some MAX value, then heapify.
: 如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
: 要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
: ，直到找到为止。
: 这么看来用balanced search tree应该更合适，klog(m)的复杂度。
h*n
22 楼
支持版主
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
s*5
23 楼
This is not right. Adding the two neighbors of the old root is not enough.
For example, to find the 4th smallest element, you need to add 3 new
elements (0,3), (2,2), (3,0) to the heap.
On average, at the k <= K step, you need to add sqrt(k) new elements to the
heap, not just two. The time complexity will be K*sqrt(K)*log(K), and the
space is O(K*sqrt(K)).
that
,
【在 g**x 的大作中提到】
: K-way merge is good. But it doesn't gain the benefits of the condition that
: each column is also in increasing order.
: How about this:
: Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
: 1)Delete the root of the heap;
: 2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
: pick up [i+1,j] and [i,j+1]).
: 3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
: The time complexity is K Log(K) (For each loop, heap size increase at most,
: so the heap size is K). It would be faster when K<
For example, to find the 4th smallest element, you need to add 3 new
elements (0,3), (2,2), (3,0) to the heap.
On average, at the k <= K step, you need to add sqrt(k) new elements to the
heap, not just two. The time complexity will be K*sqrt(K)*log(K), and the
space is O(K*sqrt(K)).
that
,
【在 g**x 的大作中提到】
: K-way merge is good. But it doesn't gain the benefits of the condition that
: each column is also in increasing order.
: How about this:
: Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
: 1)Delete the root of the heap;
: 2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
: pick up [i+1,j] and [i,j+1]).
: 3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
: The time complexity is K Log(K) (For each loop, heap size increase at most,
: so the heap size is K). It would be faster when K<
t*8
24 楼
支持
g*x
25 楼
Could you give an example?
The two neighbors of the NEW root are enough to ensure the next minimum. The
rest are larger than either the two neighbors or the existing elements in
heap.
the
【在 s***5 的大作中提到】
: This is not right. Adding the two neighbors of the old root is not enough.
: For example, to find the 4th smallest element, you need to add 3 new
: elements (0,3), (2,2), (3,0) to the heap.
: On average, at the k <= K step, you need to add sqrt(k) new elements to the
: heap, not just two. The time complexity will be K*sqrt(K)*log(K), and the
: space is O(K*sqrt(K)).
:
: that
: ,
The two neighbors of the NEW root are enough to ensure the next minimum. The
rest are larger than either the two neighbors or the existing elements in
heap.
the
【在 s***5 的大作中提到】
: This is not right. Adding the two neighbors of the old root is not enough.
: For example, to find the 4th smallest element, you need to add 3 new
: elements (0,3), (2,2), (3,0) to the heap.
: On average, at the k <= K step, you need to add sqrt(k) new elements to the
: heap, not just two. The time complexity will be K*sqrt(K)*log(K), and the
: space is O(K*sqrt(K)).
:
: that
: ,
e*4
26 楼
支持
s*5
27 楼
I double checked, and I was wrong. The only thing is that you need to check
if one of the two neighbors of the new root is already in the heap,
otherwise you add duplicated elements.
3*3 matrix
1 3 6
2 4 7
5 8 9
at k =3 when 3 is the root, you remove it and add its neighbors (4,6) to the
heap, but 4 is already in the heap since it is also the neighbor of 2.
The
【在 g**x 的大作中提到】
: Could you give an example?
: The two neighbors of the NEW root are enough to ensure the next minimum. The
: rest are larger than either the two neighbors or the existing elements in
: heap.
:
: the
if one of the two neighbors of the new root is already in the heap,
otherwise you add duplicated elements.
3*3 matrix
1 3 6
2 4 7
5 8 9
at k =3 when 3 is the root, you remove it and add its neighbors (4,6) to the
heap, but 4 is already in the heap since it is also the neighbor of 2.
The
【在 g**x 的大作中提到】
: Could you give an example?
: The two neighbors of the NEW root are enough to ensure the next minimum. The
: rest are larger than either the two neighbors or the existing elements in
: heap.
:
: the
b*r
28 楼
Ding
g*x
29 楼
Right. Cannot have duplicated elements.
check
the
【在 s***5 的大作中提到】
: I double checked, and I was wrong. The only thing is that you need to check
: if one of the two neighbors of the new root is already in the heap,
: otherwise you add duplicated elements.
: 3*3 matrix
: 1 3 6
: 2 4 7
: 5 8 9
: at k =3 when 3 is the root, you remove it and add its neighbors (4,6) to the
: heap, but 4 is already in the heap since it is also the neighbor of 2.
:
check
the
【在 s***5 的大作中提到】
: I double checked, and I was wrong. The only thing is that you need to check
: if one of the two neighbors of the new root is already in the heap,
: otherwise you add duplicated elements.
: 3*3 matrix
: 1 3 6
: 2 4 7
: 5 8 9
: at k =3 when 3 is the root, you remove it and add its neighbors (4,6) to the
: heap, but 4 is already in the heap since it is also the neighbor of 2.
:
q*o
30 楼
支持!
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
【在 k******w 的大作中提到】
: 群众的眼睛是雪亮的，三位版主对版上的贡献大家有目共睹。版上最近出现几个言语猥
: 琐之流，为泻一己私愤，肆意挑衅。言论自由，个人选择，我不妄加评论。但所有支持
: 版主的版友请楼下表达你们的支持！顶此楼进十大！
b*d
31 楼
这个解法应该可行。
run
【在 D********g 的大作中提到】
: maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
: 一个数字以及每个数字对应的行号。
: 然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
: out，change root value to some MAX value, then heapify.
: 如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
: 要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
: ，直到找到为止。
: 这么看来用balanced search tree应该更合适，klog(m)的复杂度。
run
【在 D********g 的大作中提到】
: maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
: 一个数字以及每个数字对应的行号。
: 然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
: out，change root value to some MAX value, then heapify.
: 如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
: 要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
: ，直到找到为止。
: 这么看来用balanced search tree应该更合适，klog(m)的复杂度。
x*h
32 楼
支持版主！
l*8
33 楼
what if K = m*n/2?
then Klog(K) becomes m*n*log(m*n)
that
,
【在 g**x 的大作中提到】
: K-way merge is good. But it doesn't gain the benefits of the condition that
: each column is also in increasing order.
: How about this:
: Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
: 1)Delete the root of the heap;
: 2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
: pick up [i+1,j] and [i,j+1]).
: 3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
: The time complexity is K Log(K) (For each loop, heap size increase at most,
: so the heap size is K). It would be faster when K<
then Klog(K) becomes m*n*log(m*n)
that
,
【在 g**x 的大作中提到】
: K-way merge is good. But it doesn't gain the benefits of the condition that
: each column is also in increasing order.
: How about this:
: Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
: 1)Delete the root of the heap;
: 2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
: pick up [i+1,j] and [i,j+1]).
: 3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
: The time complexity is K Log(K) (For each loop, heap size increase at most,
: so the heap size is K). It would be faster when K<
n*2
34 楼
绝对支持现任斑务
s*8
35 楼
强烈支持！！
【在 x***h 的大作中提到】
: 支持版主！
【在 x***h 的大作中提到】
: 支持版主！
c*y
36 楼
光从版主天天不辞辛劳回答大家问题来看就已经很尽责了
每贴都回 而且很多答案比律师还专业
活雷锋~~~
每贴都回 而且很多答案比律师还专业
活雷锋~~~
相关阅读
求paper一片，谢谢Papain 木瓜蛋白酶有什么具体的工业用途?谁来讲一下 耿建国北大生物系出来的，转行的有多少？版上的兄弟有没有pymol高手，请教个问题。前两天有一个找人有偿审稿的帖子呢？引用版权问题请教：跨膜蛋白的朝向paper help of ann hum genet投的论文， 怎么办呢有没有大虾普及下怎么找生物公司工作的啊？问问转校的一点事情 (转载)nih funding什么时候出结果遇到难题了，求建议不要错过：Michael Greenberg 等 扎堆报告PNAS 投稿问题credits和 semester hours 怎样换算?如果有一个蛋白问一个nickel beads问题？从脂肪细胞里面抽提DNA/RNA有没有什么窍门？