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 楼
光从版主天天不辞辛劳回答大家问题来看就已经很尽责了
每贴都回 而且很多答案比律师还专业
活雷锋~~~
每贴都回 而且很多答案比律师还专业
活雷锋~~~
相关阅读
有谁对植物牛人Elliot M Meyerowitz有了解么？明年芝加哥的AACR meeting征室友（女）八年留学回国成啃老族 海归求职受挫原因各异(ZZ)细菌养不起来怎么收到 学术杂志 关于我感兴趣的 文章的 email notice?paper request求做过erk1/2的western blot高手进来一下急求一篇paper!!! thanks!回国faculty的酸甜苦辣(ZZ)J2拿到offer想回国签J1，求教！Nature期刊家族限时促销：影响因子多少，年订费就是多少。PVDF MCE NYLON PTFE这些膜有什么大区别？想起来那年磷酸化蛋白的WESTERN BLOT问题请问怎样 pick up single conlony for stable cell line请教，这个图是用什么软件画的？做过Elispot的请进惊讶发现editors周末也上班。写屁婆这东西就象article help