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大的数。
: 请问有没有比较好的解法。
l*e
14 楼
支持,好人一生平安
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)的复杂度。
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.
:
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 楼
绝对支持现任斑务
c*y
36 楼
光从版主天天不辞辛劳回答大家问题来看就已经很尽责了
每贴都回 而且很多答案比律师还专业
活雷锋~~~
每贴都回 而且很多答案比律师还专业
活雷锋~~~
相关阅读
美国实验室能和中国实验室联合申请funding吗?包子求paper包子求paper!北大老师越来越出息了啊,开始敲诈本科生钱了 (转载)问问投药厂博后 (转载)这种事情该怎么办啊Postdoctoral Researcher Position Available at OSU中国海洋大学(青岛) 海洋生物多样性与进化研究所 诚聘英才加盟科学家的生活是 很无聊的JAMA ONCOLOGY这个杂志怎么样?有没有懂biology crystallogrphy并且会计算编程的张峰:CRISPR也可以用来编辑RNApython为何要用嵌入来表示循环求paper,谢谢!施一公官升副部级刚刚后知后觉知道西湖大学是11公等联名上书开的求real English conversationpaper help![bssd] 生物进化论领域?找博后Ngago不切linearized plasmid,韩春雨怎么解释的?