v*****k 发帖数: 7798 | 1 n个sorted数组,每个有k个元素。怎样最快找到m个最大元素?复杂度多少? |
q****x 发帖数: 7404 | 2 赞。
【在 v*****k 的大作中提到】 : n个sorted数组,每个有k个元素。怎样最快找到m个最大元素?复杂度多少?
|
v*****k 发帖数: 7798 | 3 heap显然是可以的。还可以用类似radix sort,注意最大的只需要做n个排序即可。 |
B*******1 发帖数: 2454 | 4 only one coding question? |
v*****k 发帖数: 7798 | 5 先是互相介绍,问现在干什么。
然后问了一些java的问题。reference counting, syncronized...
再就是这个问题随便讨论一下时间就到了。
【在 B*******1 的大作中提到】 : only one coding question?
|
t*********7 发帖数: 255 | |
s******n 发帖数: 226 | 7 请教如何做到O(m)?
【在 t*********7 的大作中提到】 : O(m)
|
y******u 发帖数: 804 | 8 初始时,将每个排好序的数组的最大值(共n个)压入max-heap,worst case o(nlogn)
每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn)
直到选出m个最大值
所以整体复杂度 worst 是 o((m+n)logn)
请大牛指正! |
b******g 发帖数: 1721 | |
a********m 发帖数: 15480 | 10 感觉不可能。比如m=1也要k次。
【在 b******g 的大作中提到】 : 同问,如何搞到O(m)?
|
|
|
b******g 发帖数: 1721 | 11 牛就一个字。:-)
那yiyeguhu说的o((m+n)logn)就是比较不错了吧?有没啥comments?
【在 a********m 的大作中提到】 : 感觉不可能。比如m=1也要k次。
|
E***n 发帖数: 166 | 12
nlogn)
n个元素,建堆只需要O(n)的时间,这样应该是O(m * logn + n)
【在 y******u 的大作中提到】 : 初始时,将每个排好序的数组的最大值(共n个)压入max-heap,worst case o(nlogn) : 每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn) : 直到选出m个最大值 : 所以整体复杂度 worst 是 o((m+n)logn) : 请大牛指正!
|
a********m 发帖数: 15480 | 13 错了。。。。是n次。。。习惯n是数组长度了,就没仔细看。。。
【在 b******g 的大作中提到】 : 牛就一个字。:-) : 那yiyeguhu说的o((m+n)logn)就是比较不错了吧?有没啥comments?
|
a********m 发帖数: 15480 | 14 不牛的说一句,这个方法有问题吧。至少终止条件不对,比如n=20, m = 21. 第21个数
字不一定是最大值那个数组的第二个数字。
nlogn)
【在 y******u 的大作中提到】 : 初始时,将每个排好序的数组的最大值(共n个)压入max-heap,worst case o(nlogn) : 每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn) : 直到选出m个最大值 : 所以整体复杂度 worst 是 o((m+n)logn) : 请大牛指正!
|
s******n 发帖数: 226 | 15 每次只取一个 a(当前最大),然后push a所在数组的下一个,如果数组空,任选一个
数组,选取最近的一个数
因为要选m次,所以有mlgn,再加上最开始的nlgn
【在 a********m 的大作中提到】 : 不牛的说一句,这个方法有问题吧。至少终止条件不对,比如n=20, m = 21. 第21个数 : 字不一定是最大值那个数组的第二个数字。 : : nlogn)
|
P****a 发帖数: 864 | 16 一万遍啊,建堆是O(n)的
【在 s******n 的大作中提到】 : 每次只取一个 a(当前最大),然后push a所在数组的下一个,如果数组空,任选一个 : 数组,选取最近的一个数 : 因为要选m次,所以有mlgn,再加上最开始的nlgn
|
s******n 发帖数: 226 | 17 hehe 忽略了 谢谢啦 ^ ^
【在 P****a 的大作中提到】 : 一万遍啊,建堆是O(n)的
|
a********m 发帖数: 15480 | 18 恩。这样应该是对的。
【在 s******n 的大作中提到】 : 每次只取一个 a(当前最大),然后push a所在数组的下一个,如果数组空,任选一个 : 数组,选取最近的一个数 : 因为要选m次,所以有mlgn,再加上最开始的nlgn
|
b******g 发帖数: 1721 | 19 谢谢啦,原来是你说的 O(mlogn+n)
【在 a********m 的大作中提到】 : 恩。这样应该是对的。
|
a********m 发帖数: 15480 | 20 俺是来学习的。建堆俺也不太懂,还要学。
【在 b******g 的大作中提到】 : 谢谢啦,原来是你说的 O(mlogn+n)
|
|
|
z****u 发帖数: 104 | 21 不是 O(n*logn) 么?
【在 P****a 的大作中提到】 : 一万遍啊,建堆是O(n)的
|
A**u 发帖数: 2458 | 22 不对
【在 s******n 的大作中提到】 : 每次只取一个 a(当前最大),然后push a所在数组的下一个,如果数组空,任选一个 : 数组,选取最近的一个数 : 因为要选m次,所以有mlgn,再加上最开始的nlgn
|
C***U 发帖数: 2406 | 23 你的O(m)是怎么来的?
如果可以O(m)的话就可以O(n)排序n个数字了了
在原题中去k=1,m=1, 这样就是每次找最大书数。找n次就排序了。
按照你说的,每次O(1)时间,总共O(n)时间排序了。
【在 t*********7 的大作中提到】 : O(m)
|
H*M 发帖数: 1268 | 24 并不是说heap里有21个数字就不往里面push了的,终止条件是pop出21个数字
每次pop出来一个最大的数,也必须此数所在的数组的下一个push进去
所以你所说的,第21个数字不一定是最大值那个数组的第二个没错,但是再pop第二大
数字的时候,也会把其他的压进去的。
【在 a********m 的大作中提到】 : 不牛的说一句,这个方法有问题吧。至少终止条件不对,比如n=20, m = 21. 第21个数 : 字不一定是最大值那个数组的第二个数字。 : : nlogn)
|
x*******7 发帖数: 223 | 25 应该是minheap吧,不是max heap.
【在 H*M 的大作中提到】 : 并不是说heap里有21个数字就不往里面push了的,终止条件是pop出21个数字 : 每次pop出来一个最大的数,也必须此数所在的数组的下一个push进去 : 所以你所说的,第21个数字不一定是最大值那个数组的第二个没错,但是再pop第二大 : 数字的时候,也会把其他的压进去的。
|
H*M 发帖数: 1268 | 26 为啥是minheap? 是max 吧。保持每行最大值在里面 ,每次pop出的都是最大的
【在 x*******7 的大作中提到】 : 应该是minheap吧,不是max heap.
|
k****n 发帖数: 369 | 27 说的可能是两回事,求k个最大值的话
如果是用一个k个元素的heap,那应该是minheap
每次把当前最小值扔掉,剩下的是大的
如果是整个数组heapify的话,那就是maxheap了
【在 H*M 的大作中提到】 : 为啥是minheap? 是max 吧。保持每行最大值在里面 ,每次pop出的都是最大的
|
H*M 发帖数: 1268 | 28 这两个都跟本题目无关锕
【在 k****n 的大作中提到】 : 说的可能是两回事,求k个最大值的话 : 如果是用一个k个元素的heap,那应该是minheap : 每次把当前最小值扔掉,剩下的是大的 : 如果是整个数组heapify的话,那就是maxheap了
|
k****n 发帖数: 369 | 29 哈哈哈,看错了。。。
如果是m个最大元素,用k-way merge的办法的话,的确就是maxheap了
【在 H*M 的大作中提到】 : 这两个都跟本题目无关锕
|
s******n 发帖数: 226 | 30 I thought this is a very basic question, and you can find from many books.
Why there will be so many disagreement? |
|
|
d*******d 发帖数: 2050 | 31 这个问题有两种解答,你答得时候要看面试官想听哪个:
1: k-way merge sort, 用heap
2: binary search.
code大家自己写吧.
【在 v*****k 的大作中提到】 : n个sorted数组,每个有k个元素。怎样最快找到m个最大元素?复杂度多少?
|
B*******1 发帖数: 2454 | 32 binary search 怎么搞?
好久不看大牛你发帖子了啊。
【在 d*******d 的大作中提到】 : 这个问题有两种解答,你答得时候要看面试官想听哪个: : 1: k-way merge sort, 用heap : 2: binary search. : code大家自己写吧.
|
d*******d 发帖数: 2050 | 33 最近事太多,又是回国,又是面试,没功夫上网了.
回头要据几个拽公司offer替大家报仇.
【在 B*******1 的大作中提到】 : binary search 怎么搞? : 好久不看大牛你发帖子了啊。
|
b*******y 发帖数: 232 | 34 orz,牛
【在 d*******d 的大作中提到】 : 最近事太多,又是回国,又是面试,没功夫上网了. : 回头要据几个拽公司offer替大家报仇.
|
d*******d 发帖数: 2050 | 35 2:b-search
找到最小的那个数,使得每个array里面不小于该数的数的个数的和至少为m.
【在 B*******1 的大作中提到】 : binary search 怎么搞? : 好久不看大牛你发帖子了啊。
|
e****r 发帖数: 28 | 36 good arguments, 秋虫.
【在 a********m 的大作中提到】 : 感觉不可能。比如m=1也要k次。
|
h*****n 发帖数: 93 | 37 谦虚的过分了.连google的大牛都这么谦虚!
【在 a********m 的大作中提到】 : 俺是来学习的。建堆俺也不太懂,还要学。
|
v*****k 发帖数: 7798 | 38 n个sorted数组,每个有k个元素。怎样最快找到m个最大元素?复杂度多少? |
q****x 发帖数: 7404 | 39 赞。
【在 v*****k 的大作中提到】 : n个sorted数组,每个有k个元素。怎样最快找到m个最大元素?复杂度多少?
|
v*****k 发帖数: 7798 | 40 heap显然是可以的。还可以用类似radix sort,注意最大的只需要做n个排序即可。 |
|
|
B*******1 发帖数: 2454 | 41 only one coding question? |
v*****k 发帖数: 7798 | 42 先是互相介绍,问现在干什么。
然后问了一些java的问题。reference counting, syncronized...
再就是这个问题随便讨论一下时间就到了。
【在 B*******1 的大作中提到】 : only one coding question?
|
t*********7 发帖数: 255 | |
s******n 发帖数: 226 | 44 请教如何做到O(m)?
【在 t*********7 的大作中提到】 : O(m)
|
y******u 发帖数: 804 | 45 初始时,将每个排好序的数组的最大值(共n个)压入max-heap,worst case o(nlogn)
每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn)
直到选出m个最大值
所以整体复杂度 worst 是 o((m+n)logn)
请大牛指正! |
b******g 发帖数: 1721 | |
a********m 发帖数: 15480 | 47 感觉不可能。比如m=1也要k次。
【在 b******g 的大作中提到】 : 同问,如何搞到O(m)?
|
b******g 发帖数: 1721 | 48 牛就一个字。:-)
那yiyeguhu说的o((m+n)logn)就是比较不错了吧?有没啥comments?
【在 a********m 的大作中提到】 : 感觉不可能。比如m=1也要k次。
|
E***n 发帖数: 166 | 49
nlogn)
n个元素,建堆只需要O(n)的时间,这样应该是O(m * logn + n)
【在 y******u 的大作中提到】 : 初始时,将每个排好序的数组的最大值(共n个)压入max-heap,worst case o(nlogn) : 每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn) : 直到选出m个最大值 : 所以整体复杂度 worst 是 o((m+n)logn) : 请大牛指正!
|
a********m 发帖数: 15480 | 50 错了。。。。是n次。。。习惯n是数组长度了,就没仔细看。。。
【在 b******g 的大作中提到】 : 牛就一个字。:-) : 那yiyeguhu说的o((m+n)logn)就是比较不错了吧?有没啥comments?
|
|
|
a********m 发帖数: 15480 | 51 不牛的说一句,这个方法有问题吧。至少终止条件不对,比如n=20, m = 21. 第21个数
字不一定是最大值那个数组的第二个数字。
nlogn)
【在 y******u 的大作中提到】 : 初始时,将每个排好序的数组的最大值(共n个)压入max-heap,worst case o(nlogn) : 每次pop最大值,补进最大值所在数组的次大值 worst (logn)+(logn) : 直到选出m个最大值 : 所以整体复杂度 worst 是 o((m+n)logn) : 请大牛指正!
|
s******n 发帖数: 226 | 52 每次只取一个 a(当前最大),然后push a所在数组的下一个,如果数组空,任选一个
数组,选取最近的一个数
因为要选m次,所以有mlgn,再加上最开始的nlgn
【在 a********m 的大作中提到】 : 不牛的说一句,这个方法有问题吧。至少终止条件不对,比如n=20, m = 21. 第21个数 : 字不一定是最大值那个数组的第二个数字。 : : nlogn)
|
P****a 发帖数: 864 | 53 一万遍啊,建堆是O(n)的
【在 s******n 的大作中提到】 : 每次只取一个 a(当前最大),然后push a所在数组的下一个,如果数组空,任选一个 : 数组,选取最近的一个数 : 因为要选m次,所以有mlgn,再加上最开始的nlgn
|
s******n 发帖数: 226 | 54 hehe 忽略了 谢谢啦 ^ ^
【在 P****a 的大作中提到】 : 一万遍啊,建堆是O(n)的
|
a********m 发帖数: 15480 | 55 恩。这样应该是对的。
【在 s******n 的大作中提到】 : 每次只取一个 a(当前最大),然后push a所在数组的下一个,如果数组空,任选一个 : 数组,选取最近的一个数 : 因为要选m次,所以有mlgn,再加上最开始的nlgn
|
b******g 发帖数: 1721 | 56 谢谢啦,原来是你说的 O(mlogn+n)
【在 a********m 的大作中提到】 : 恩。这样应该是对的。
|
a********m 发帖数: 15480 | 57 俺是来学习的。建堆俺也不太懂,还要学。
【在 b******g 的大作中提到】 : 谢谢啦,原来是你说的 O(mlogn+n)
|
A**u 发帖数: 2458 | 58 不对
【在 s******n 的大作中提到】 : 每次只取一个 a(当前最大),然后push a所在数组的下一个,如果数组空,任选一个 : 数组,选取最近的一个数 : 因为要选m次,所以有mlgn,再加上最开始的nlgn
|
C***U 发帖数: 2406 | 59 你的O(m)是怎么来的?
如果可以O(m)的话就可以O(n)排序n个数字了了
在原题中去k=1,m=1, 这样就是每次找最大书数。找n次就排序了。
按照你说的,每次O(1)时间,总共O(n)时间排序了。
【在 t*********7 的大作中提到】 : O(m)
|
x*******7 发帖数: 223 | 60 应该是minheap吧,不是max heap.
【在 H*M 的大作中提到】 : 并不是说heap里有21个数字就不往里面push了的,终止条件是pop出21个数字 : 每次pop出来一个最大的数,也必须此数所在的数组的下一个push进去 : 所以你所说的,第21个数字不一定是最大值那个数组的第二个没错,但是再pop第二大 : 数字的时候,也会把其他的压进去的。
|
|
|
H*M 发帖数: 1268 | 61 为啥是minheap? 是max 吧。保持每行最大值在里面 ,每次pop出的都是最大的
【在 x*******7 的大作中提到】 : 应该是minheap吧,不是max heap.
|
k****n 发帖数: 369 | 62 说的可能是两回事,求k个最大值的话
如果是用一个k个元素的heap,那应该是minheap
每次把当前最小值扔掉,剩下的是大的
如果是整个数组heapify的话,那就是maxheap了
【在 H*M 的大作中提到】 : 为啥是minheap? 是max 吧。保持每行最大值在里面 ,每次pop出的都是最大的
|
H*M 发帖数: 1268 | 63 这两个都跟本题目无关锕
【在 k****n 的大作中提到】 : 说的可能是两回事,求k个最大值的话 : 如果是用一个k个元素的heap,那应该是minheap : 每次把当前最小值扔掉,剩下的是大的 : 如果是整个数组heapify的话,那就是maxheap了
|
k****n 发帖数: 369 | 64 哈哈哈,看错了。。。
如果是m个最大元素,用k-way merge的办法的话,的确就是maxheap了
【在 H*M 的大作中提到】 : 这两个都跟本题目无关锕
|
s******n 发帖数: 226 | 65 I thought this is a very basic question, and you can find from many books.
Why there will be so many disagreement? |
d*******d 发帖数: 2050 | 66 这个问题有两种解答,你答得时候要看面试官想听哪个:
1: k-way merge sort, 用heap
2: binary search.
code大家自己写吧.
【在 v*****k 的大作中提到】 : n个sorted数组,每个有k个元素。怎样最快找到m个最大元素?复杂度多少?
|
B*******1 发帖数: 2454 | 67 binary search 怎么搞?
好久不看大牛你发帖子了啊。
【在 d*******d 的大作中提到】 : 这个问题有两种解答,你答得时候要看面试官想听哪个: : 1: k-way merge sort, 用heap : 2: binary search. : code大家自己写吧.
|
d*******d 发帖数: 2050 | 68 最近事太多,又是回国,又是面试,没功夫上网了.
回头要据几个拽公司offer替大家报仇.
【在 B*******1 的大作中提到】 : binary search 怎么搞? : 好久不看大牛你发帖子了啊。
|
b*******y 发帖数: 232 | 69 orz,牛
【在 d*******d 的大作中提到】 : 最近事太多,又是回国,又是面试,没功夫上网了. : 回头要据几个拽公司offer替大家报仇.
|
d*******d 发帖数: 2050 | 70 2:b-search
找到最小的那个数,使得每个array里面不小于该数的数的个数的和至少为m.
【在 B*******1 的大作中提到】 : binary search 怎么搞? : 好久不看大牛你发帖子了啊。
|
|
|
e****r 发帖数: 28 | 71 good arguments, 秋虫.
【在 a********m 的大作中提到】 : 感觉不可能。比如m=1也要k次。
|
h*****n 发帖数: 93 | 72 谦虚的过分了.连google的大牛都这么谦虚!
【在 a********m 的大作中提到】 : 俺是来学习的。建堆俺也不太懂,还要学。
|
T****y 发帖数: 36 | |
b********r 发帖数: 118 | 74 agree
【在 T****y 的大作中提到】 : 应该是 n+mlog(n)
|
w****x 发帖数: 2483 | 75 Build heap O(n),
每次更新heap->log(n)共m次 -> n + mlogn |
f***s 发帖数: 112 | 76 大家给看看
1.对于N个数组的最大元素排序建二叉树,树除了左右指针还有一个指针指向对应的
ARRAY
2.取一个最大元素(最右叶节点),更新节点为对应次大值,摘除并且重新插入上面的
二叉树,直到K个值都被耗尽。(存在重新平衡树的要求)
3.重复2.)直到 m个节点都得到了返回。
复杂度 1) nlgn 2)单个需要 lgn 总体最坏 (m-1)lgn
加起来 O((m+n)lgn)
1.因为N个数组都是SORTED,每次取得单个数组的最大值是CONSTANT time
2
【在 A**u 的大作中提到】 : 不对
|