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 的大作中提到】
: 不对
|
