v*k
3 楼
heap显然是可以的。还可以用类似radix sort,注意最大的只需要做n个排序即可。
B*1
4 楼
only one coding question?
t*7
6 楼
O(m)
y*u
8 楼
初始时,将每个排好序的数组的最大值(共n个)压入max-heap,worst case o(nlogn)
每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn)
直到选出m个最大值
所以整体复杂度 worst 是 o((m+n)logn)
请大牛指正!
每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn)
直到选出m个最大值
所以整体复杂度 worst 是 o((m+n)logn)
请大牛指正!
b*g
9 楼
同问,如何搞到O(m)?
s*n
30 楼
I thought this is a very basic question, and you can find from many books.
Why there will be so many disagreement?
Why there will be so many disagreement?
v*k
38 楼
n个sorted数组,每个有k个元素。怎样最快找到m个最大元素?复杂度多少?
v*k
40 楼
heap显然是可以的。还可以用类似radix sort,注意最大的只需要做n个排序即可。
B*1
41 楼
only one coding question?
t*7
43 楼
O(m)
y*u
45 楼
初始时,将每个排好序的数组的最大值(共n个)压入max-heap,worst case o(nlogn)
每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn)
直到选出m个最大值
所以整体复杂度 worst 是 o((m+n)logn)
请大牛指正!
每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn)
直到选出m个最大值
所以整体复杂度 worst 是 o((m+n)logn)
请大牛指正!
b*g
46 楼
同问,如何搞到O(m)?
s*n
65 楼
I thought this is a very basic question, and you can find from many books.
Why there will be so many disagreement?
Why there will be so many disagreement?
T*y
73 楼
应该是 n+mlog(n)
w*x
75 楼
Build heap O(n),
每次更新heap->log(n)共m次 -> n + mlogn
每次更新heap->log(n)共m次 -> n + mlogn
相关阅读
H1-B材料准备,律师说不用I-20?Contractor job 異地電話面試如何判斷公司好壞已经file了的regular processing H1b transfer能改成premium processing 吗?求bless, 明天onsite dream job希望下周谈offer 顺利 求祝福兼答谢本版Are headhunters really helpful in your job hunting?如果公司已经要求references,是不是已经算比较靠谱了?大家觉得我有必要去办H1B么问一道算法题华盛顿州和加州工资比较想问问Contactor申请H1B签证的事被hr耍了Python 里有类似 Sprintf 的函数么?请教关于opt 前3个月必须找到工作的问题关于singleton 的面试题two week notice 什么时候提?为什么老死在HR的电面上请教没有工作能否申请ssn有人听说过SAG这个公司吗?我是遇到骗子了吗?攒rp,我今天的面试教训,一个很小的细节