q*x
2 楼
赞。
【在 v*****k 的大作中提到】
: n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
【在 v*****k 的大作中提到】
: n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
v*k
3 楼
heap显然是可以的。还可以用类似radix sort，注意最大的只需要做n个排序即可。
B*1
4 楼
only one coding question?
v*k
5 楼
先是互相介绍，问现在干什么。
然后问了一些java的问题。reference counting， syncronized...
再就是这个问题随便讨论一下时间就到了。
【在 B*******1 的大作中提到】
: only one coding question?
然后问了一些java的问题。reference counting， syncronized...
再就是这个问题随便讨论一下时间就到了。
【在 B*******1 的大作中提到】
: only one coding question?
t*7
6 楼
O(m)
s*n
7 楼
请教如何做到O(m)?
【在 t*********7 的大作中提到】
: O(m)
【在 t*********7 的大作中提到】
: 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）？
a*m
10 楼
感觉不可能。比如m=1也要k次。
【在 b******g 的大作中提到】
: 同问，如何搞到O（m）？
【在 b******g 的大作中提到】
: 同问，如何搞到O（m）？
b*g
11 楼
牛就一个字。:-)
那yiyeguhu说的o(（m+n）logn）就是比较不错了吧？有没啥comments?
【在 a********m 的大作中提到】
: 感觉不可能。比如m=1也要k次。
那yiyeguhu说的o(（m+n）logn）就是比较不错了吧？有没啥comments?
【在 a********m 的大作中提到】
: 感觉不可能。比如m=1也要k次。
E*n
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
13 楼
错了。。。。是n次。。。习惯n是数组长度了，就没仔细看。。。
【在 b******g 的大作中提到】
: 牛就一个字。:-)
: 那yiyeguhu说的o(（m+n）logn）就是比较不错了吧？有没啥comments?
【在 b******g 的大作中提到】
: 牛就一个字。:-)
: 那yiyeguhu说的o(（m+n）logn）就是比较不错了吧？有没啥comments?
a*m
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）
: 请大牛指正！
字不一定是最大值那个数组的第二个数字。
nlogn)
【在 y******u 的大作中提到】
: 初始时，将每个排好序的数组的最大值（共n个）压入max－heap，worst case o(nlogn)
: 每次pop最大值，补进最大值所在数组的次大值 worst (logn)+(logn)
: 直到选出m个最大值
: 所以整体复杂度 worst 是 o(（m+n）logn）
: 请大牛指正！
s*n
15 楼
每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
数组，选取最近的一个数
因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 a********m 的大作中提到】
: 不牛的说一句，这个方法有问题吧。至少终止条件不对，比如n=20, m = 21. 第21个数
: 字不一定是最大值那个数组的第二个数字。
:
: nlogn)
数组，选取最近的一个数
因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 a********m 的大作中提到】
: 不牛的说一句，这个方法有问题吧。至少终止条件不对，比如n=20, m = 21. 第21个数
: 字不一定是最大值那个数组的第二个数字。
:
: nlogn)
P*a
16 楼
一万遍啊，建堆是O(n)的
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
s*n
17 楼
hehe 忽略了 谢谢啦 ^ ^
【在 P****a 的大作中提到】
: 一万遍啊，建堆是O(n)的
【在 P****a 的大作中提到】
: 一万遍啊，建堆是O(n)的
a*m
18 楼
恩。这样应该是对的。
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
b*g
19 楼
谢谢啦，原来是你说的 O(mlogn+n)
【在 a********m 的大作中提到】
: 恩。这样应该是对的。
【在 a********m 的大作中提到】
: 恩。这样应该是对的。
a*m
20 楼
俺是来学习的。建堆俺也不太懂，还要学。
【在 b******g 的大作中提到】
: 谢谢啦，原来是你说的 O(mlogn+n)
【在 b******g 的大作中提到】
: 谢谢啦，原来是你说的 O(mlogn+n)
z*u
21 楼
不是 O(n*logn) 么？
【在 P****a 的大作中提到】
: 一万遍啊，建堆是O(n)的
【在 P****a 的大作中提到】
: 一万遍啊，建堆是O(n)的
A*u
22 楼
不对
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
C*U
23 楼
你的O(m)是怎么来的？
如果可以O(m)的话就可以O(n)排序n个数字了了
在原题中去k=1,m=1, 这样就是每次找最大书数。找n次就排序了。
按照你说的，每次O(1)时间，总共O(n)时间排序了。
【在 t*********7 的大作中提到】
: O(m)
如果可以O(m)的话就可以O(n)排序n个数字了了
在原题中去k=1,m=1, 这样就是每次找最大书数。找n次就排序了。
按照你说的，每次O(1)时间，总共O(n)时间排序了。
【在 t*********7 的大作中提到】
: O(m)
H*M
24 楼
并不是说heap里有21个数字就不往里面push了的，终止条件是pop出21个数字
每次pop出来一个最大的数，也必须此数所在的数组的下一个push进去
所以你所说的，第21个数字不一定是最大值那个数组的第二个没错，但是再pop第二大
数字的时候，也会把其他的压进去的。
【在 a********m 的大作中提到】
: 不牛的说一句，这个方法有问题吧。至少终止条件不对，比如n=20, m = 21. 第21个数
: 字不一定是最大值那个数组的第二个数字。
:
: nlogn)
每次pop出来一个最大的数，也必须此数所在的数组的下一个push进去
所以你所说的，第21个数字不一定是最大值那个数组的第二个没错，但是再pop第二大
数字的时候，也会把其他的压进去的。
【在 a********m 的大作中提到】
: 不牛的说一句，这个方法有问题吧。至少终止条件不对，比如n=20, m = 21. 第21个数
: 字不一定是最大值那个数组的第二个数字。
:
: nlogn)
x*7
25 楼
应该是minheap吧，不是max heap.
【在 H*M 的大作中提到】
: 并不是说heap里有21个数字就不往里面push了的，终止条件是pop出21个数字
: 每次pop出来一个最大的数，也必须此数所在的数组的下一个push进去
: 所以你所说的，第21个数字不一定是最大值那个数组的第二个没错，但是再pop第二大
: 数字的时候，也会把其他的压进去的。
【在 H*M 的大作中提到】
: 并不是说heap里有21个数字就不往里面push了的，终止条件是pop出21个数字
: 每次pop出来一个最大的数，也必须此数所在的数组的下一个push进去
: 所以你所说的，第21个数字不一定是最大值那个数组的第二个没错，但是再pop第二大
: 数字的时候，也会把其他的压进去的。
H*M
26 楼
为啥是minheap? 是max 吧。保持每行最大值在里面 ，每次pop出的都是最大的
【在 x*******7 的大作中提到】
: 应该是minheap吧，不是max heap.
【在 x*******7 的大作中提到】
: 应该是minheap吧，不是max heap.
k*n
27 楼
说的可能是两回事，求k个最大值的话
如果是用一个k个元素的heap，那应该是minheap
每次把当前最小值扔掉，剩下的是大的
如果是整个数组heapify的话，那就是maxheap了
【在 H*M 的大作中提到】
: 为啥是minheap? 是max 吧。保持每行最大值在里面 ，每次pop出的都是最大的
如果是用一个k个元素的heap，那应该是minheap
每次把当前最小值扔掉，剩下的是大的
如果是整个数组heapify的话，那就是maxheap了
【在 H*M 的大作中提到】
: 为啥是minheap? 是max 吧。保持每行最大值在里面 ，每次pop出的都是最大的
H*M
28 楼
这两个都跟本题目无关锕
【在 k****n 的大作中提到】
: 说的可能是两回事，求k个最大值的话
: 如果是用一个k个元素的heap，那应该是minheap
: 每次把当前最小值扔掉，剩下的是大的
: 如果是整个数组heapify的话，那就是maxheap了
【在 k****n 的大作中提到】
: 说的可能是两回事，求k个最大值的话
: 如果是用一个k个元素的heap，那应该是minheap
: 每次把当前最小值扔掉，剩下的是大的
: 如果是整个数组heapify的话，那就是maxheap了
k*n
29 楼
哈哈哈，看错了。。。
如果是m个最大元素，用k-way merge的办法的话，的确就是maxheap了
【在 H*M 的大作中提到】
: 这两个都跟本题目无关锕
如果是m个最大元素，用k-way merge的办法的话，的确就是maxheap了
【在 H*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?
d*d
31 楼
这个问题有两种解答,你答得时候要看面试官想听哪个:
1: k-way merge sort, 用heap
2: binary search.
code大家自己写吧.
【在 v*****k 的大作中提到】
: n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
1: k-way merge sort, 用heap
2: binary search.
code大家自己写吧.
【在 v*****k 的大作中提到】
: n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
B*1
32 楼
binary search 怎么搞？
好久不看大牛你发帖子了啊。
【在 d*******d 的大作中提到】
: 这个问题有两种解答,你答得时候要看面试官想听哪个:
: 1: k-way merge sort, 用heap
: 2: binary search.
: code大家自己写吧.
好久不看大牛你发帖子了啊。
【在 d*******d 的大作中提到】
: 这个问题有两种解答,你答得时候要看面试官想听哪个:
: 1: k-way merge sort, 用heap
: 2: binary search.
: code大家自己写吧.
d*d
33 楼
最近事太多,又是回国,又是面试,没功夫上网了.
回头要据几个拽公司offer替大家报仇.
【在 B*******1 的大作中提到】
: binary search 怎么搞？
: 好久不看大牛你发帖子了啊。
回头要据几个拽公司offer替大家报仇.
【在 B*******1 的大作中提到】
: binary search 怎么搞？
: 好久不看大牛你发帖子了啊。
b*y
34 楼
orz，牛
【在 d*******d 的大作中提到】
: 最近事太多,又是回国,又是面试,没功夫上网了.
: 回头要据几个拽公司offer替大家报仇.
【在 d*******d 的大作中提到】
: 最近事太多,又是回国,又是面试,没功夫上网了.
: 回头要据几个拽公司offer替大家报仇.
d*d
35 楼
2:b-search
找到最小的那个数,使得每个array里面不小于该数的数的个数的和至少为m.
【在 B*******1 的大作中提到】
: binary search 怎么搞？
: 好久不看大牛你发帖子了啊。
找到最小的那个数,使得每个array里面不小于该数的数的个数的和至少为m.
【在 B*******1 的大作中提到】
: binary search 怎么搞？
: 好久不看大牛你发帖子了啊。
e*r
36 楼
good arguments, 秋虫.
【在 a********m 的大作中提到】
: 感觉不可能。比如m=1也要k次。
【在 a********m 的大作中提到】
: 感觉不可能。比如m=1也要k次。
h*n
37 楼
谦虚的过分了.连google的大牛都这么谦虚!
【在 a********m 的大作中提到】
: 俺是来学习的。建堆俺也不太懂，还要学。
【在 a********m 的大作中提到】
: 俺是来学习的。建堆俺也不太懂，还要学。
v*k
38 楼
n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
q*x
39 楼
赞。
【在 v*****k 的大作中提到】
: n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
【在 v*****k 的大作中提到】
: n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
v*k
40 楼
heap显然是可以的。还可以用类似radix sort，注意最大的只需要做n个排序即可。
B*1
41 楼
only one coding question?
v*k
42 楼
先是互相介绍，问现在干什么。
然后问了一些java的问题。reference counting， syncronized...
再就是这个问题随便讨论一下时间就到了。
【在 B*******1 的大作中提到】
: only one coding question?
然后问了一些java的问题。reference counting， syncronized...
再就是这个问题随便讨论一下时间就到了。
【在 B*******1 的大作中提到】
: only one coding question?
t*7
43 楼
O(m)
s*n
44 楼
请教如何做到O(m)?
【在 t*********7 的大作中提到】
: O(m)
【在 t*********7 的大作中提到】
: 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）？
a*m
47 楼
感觉不可能。比如m=1也要k次。
【在 b******g 的大作中提到】
: 同问，如何搞到O（m）？
【在 b******g 的大作中提到】
: 同问，如何搞到O（m）？
b*g
48 楼
牛就一个字。:-)
那yiyeguhu说的o(（m+n）logn）就是比较不错了吧？有没啥comments?
【在 a********m 的大作中提到】
: 感觉不可能。比如m=1也要k次。
那yiyeguhu说的o(（m+n）logn）就是比较不错了吧？有没啥comments?
【在 a********m 的大作中提到】
: 感觉不可能。比如m=1也要k次。
E*n
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
50 楼
错了。。。。是n次。。。习惯n是数组长度了，就没仔细看。。。
【在 b******g 的大作中提到】
: 牛就一个字。:-)
: 那yiyeguhu说的o(（m+n）logn）就是比较不错了吧？有没啥comments?
【在 b******g 的大作中提到】
: 牛就一个字。:-)
: 那yiyeguhu说的o(（m+n）logn）就是比较不错了吧？有没啥comments?
a*m
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）
: 请大牛指正！
字不一定是最大值那个数组的第二个数字。
nlogn)
【在 y******u 的大作中提到】
: 初始时，将每个排好序的数组的最大值（共n个）压入max－heap，worst case o(nlogn)
: 每次pop最大值，补进最大值所在数组的次大值 worst (logn)+(logn)
: 直到选出m个最大值
: 所以整体复杂度 worst 是 o(（m+n）logn）
: 请大牛指正！
s*n
52 楼
每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
数组，选取最近的一个数
因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 a********m 的大作中提到】
: 不牛的说一句，这个方法有问题吧。至少终止条件不对，比如n=20, m = 21. 第21个数
: 字不一定是最大值那个数组的第二个数字。
:
: nlogn)
数组，选取最近的一个数
因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 a********m 的大作中提到】
: 不牛的说一句，这个方法有问题吧。至少终止条件不对，比如n=20, m = 21. 第21个数
: 字不一定是最大值那个数组的第二个数字。
:
: nlogn)
P*a
53 楼
一万遍啊，建堆是O(n)的
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
s*n
54 楼
hehe 忽略了 谢谢啦 ^ ^
【在 P****a 的大作中提到】
: 一万遍啊，建堆是O(n)的
【在 P****a 的大作中提到】
: 一万遍啊，建堆是O(n)的
a*m
55 楼
恩。这样应该是对的。
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
b*g
56 楼
谢谢啦，原来是你说的 O(mlogn+n)
【在 a********m 的大作中提到】
: 恩。这样应该是对的。
【在 a********m 的大作中提到】
: 恩。这样应该是对的。
a*m
57 楼
俺是来学习的。建堆俺也不太懂，还要学。
【在 b******g 的大作中提到】
: 谢谢啦，原来是你说的 O(mlogn+n)
【在 b******g 的大作中提到】
: 谢谢啦，原来是你说的 O(mlogn+n)
A*u
58 楼
不对
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
【在 s******n 的大作中提到】
: 每次只取一个 a（当前最大），然后push a所在数组的下一个，如果数组空，任选一个
: 数组，选取最近的一个数
: 因为要选m次，所以有mlgn,再加上最开始的nlgn
C*U
59 楼
你的O(m)是怎么来的？
如果可以O(m)的话就可以O(n)排序n个数字了了
在原题中去k=1,m=1, 这样就是每次找最大书数。找n次就排序了。
按照你说的，每次O(1)时间，总共O(n)时间排序了。
【在 t*********7 的大作中提到】
: O(m)
如果可以O(m)的话就可以O(n)排序n个数字了了
在原题中去k=1,m=1, 这样就是每次找最大书数。找n次就排序了。
按照你说的，每次O(1)时间，总共O(n)时间排序了。
【在 t*********7 的大作中提到】
: O(m)
x*7
60 楼
应该是minheap吧，不是max heap.
【在 H*M 的大作中提到】
: 并不是说heap里有21个数字就不往里面push了的，终止条件是pop出21个数字
: 每次pop出来一个最大的数，也必须此数所在的数组的下一个push进去
: 所以你所说的，第21个数字不一定是最大值那个数组的第二个没错，但是再pop第二大
: 数字的时候，也会把其他的压进去的。
【在 H*M 的大作中提到】
: 并不是说heap里有21个数字就不往里面push了的，终止条件是pop出21个数字
: 每次pop出来一个最大的数，也必须此数所在的数组的下一个push进去
: 所以你所说的，第21个数字不一定是最大值那个数组的第二个没错，但是再pop第二大
: 数字的时候，也会把其他的压进去的。
H*M
61 楼
为啥是minheap? 是max 吧。保持每行最大值在里面 ，每次pop出的都是最大的
【在 x*******7 的大作中提到】
: 应该是minheap吧，不是max heap.
【在 x*******7 的大作中提到】
: 应该是minheap吧，不是max heap.
k*n
62 楼
说的可能是两回事，求k个最大值的话
如果是用一个k个元素的heap，那应该是minheap
每次把当前最小值扔掉，剩下的是大的
如果是整个数组heapify的话，那就是maxheap了
【在 H*M 的大作中提到】
: 为啥是minheap? 是max 吧。保持每行最大值在里面 ，每次pop出的都是最大的
如果是用一个k个元素的heap，那应该是minheap
每次把当前最小值扔掉，剩下的是大的
如果是整个数组heapify的话，那就是maxheap了
【在 H*M 的大作中提到】
: 为啥是minheap? 是max 吧。保持每行最大值在里面 ，每次pop出的都是最大的
H*M
63 楼
这两个都跟本题目无关锕
【在 k****n 的大作中提到】
: 说的可能是两回事，求k个最大值的话
: 如果是用一个k个元素的heap，那应该是minheap
: 每次把当前最小值扔掉，剩下的是大的
: 如果是整个数组heapify的话，那就是maxheap了
【在 k****n 的大作中提到】
: 说的可能是两回事，求k个最大值的话
: 如果是用一个k个元素的heap，那应该是minheap
: 每次把当前最小值扔掉，剩下的是大的
: 如果是整个数组heapify的话，那就是maxheap了
k*n
64 楼
哈哈哈，看错了。。。
如果是m个最大元素，用k-way merge的办法的话，的确就是maxheap了
【在 H*M 的大作中提到】
: 这两个都跟本题目无关锕
如果是m个最大元素，用k-way merge的办法的话，的确就是maxheap了
【在 H*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?
d*d
66 楼
这个问题有两种解答,你答得时候要看面试官想听哪个:
1: k-way merge sort, 用heap
2: binary search.
code大家自己写吧.
【在 v*****k 的大作中提到】
: n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
1: k-way merge sort, 用heap
2: binary search.
code大家自己写吧.
【在 v*****k 的大作中提到】
: n个sorted数组，每个有k个元素。怎样最快找到m个最大元素？复杂度多少？
B*1
67 楼
binary search 怎么搞？
好久不看大牛你发帖子了啊。
【在 d*******d 的大作中提到】
: 这个问题有两种解答,你答得时候要看面试官想听哪个:
: 1: k-way merge sort, 用heap
: 2: binary search.
: code大家自己写吧.
好久不看大牛你发帖子了啊。
【在 d*******d 的大作中提到】
: 这个问题有两种解答,你答得时候要看面试官想听哪个:
: 1: k-way merge sort, 用heap
: 2: binary search.
: code大家自己写吧.
d*d
68 楼
最近事太多,又是回国,又是面试,没功夫上网了.
回头要据几个拽公司offer替大家报仇.
【在 B*******1 的大作中提到】
: binary search 怎么搞？
: 好久不看大牛你发帖子了啊。
回头要据几个拽公司offer替大家报仇.
【在 B*******1 的大作中提到】
: binary search 怎么搞？
: 好久不看大牛你发帖子了啊。
b*y
69 楼
orz，牛
【在 d*******d 的大作中提到】
: 最近事太多,又是回国,又是面试,没功夫上网了.
: 回头要据几个拽公司offer替大家报仇.
【在 d*******d 的大作中提到】
: 最近事太多,又是回国,又是面试,没功夫上网了.
: 回头要据几个拽公司offer替大家报仇.
d*d
70 楼
2:b-search
找到最小的那个数,使得每个array里面不小于该数的数的个数的和至少为m.
【在 B*******1 的大作中提到】
: binary search 怎么搞？
: 好久不看大牛你发帖子了啊。
找到最小的那个数,使得每个array里面不小于该数的数的个数的和至少为m.
【在 B*******1 的大作中提到】
: binary search 怎么搞？
: 好久不看大牛你发帖子了啊。
e*r
71 楼
good arguments, 秋虫.
【在 a********m 的大作中提到】
: 感觉不可能。比如m=1也要k次。
【在 a********m 的大作中提到】
: 感觉不可能。比如m=1也要k次。
h*n
72 楼
谦虚的过分了.连google的大牛都这么谦虚!
【在 a********m 的大作中提到】
: 俺是来学习的。建堆俺也不太懂，还要学。
【在 a********m 的大作中提到】
: 俺是来学习的。建堆俺也不太懂，还要学。
T*y
73 楼
应该是 n+mlog(n)
b*r
74 楼
agree
【在 T****y 的大作中提到】
: 应该是 n+mlog(n)
【在 T****y 的大作中提到】
: 应该是 n+mlog(n)
w*x
75 楼
Build heap O(n),
每次更新heap->log(n)共m次 -> n + mlogn
每次更新heap->log(n)共m次 -> n + mlogn
f*s
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 的大作中提到】
: 不对
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 的大作中提到】
: 不对
相关阅读
H1B 被雷，求建议和经验分享如果中国和美国互联网企业在第三战场战斗谁能赢？除了内推，哪里网站找工作靠谱？一公司给了offer，我签了，现在想悔约，有啥后果？职业规划 求建议大家每天工作多久？求个混出头的方向， 迷茫啊。。。一个湾区烂startup的短暂体验gmail/google 搜索问题，你一定也遇到过Uber连夜发布合并奖励邮件CEO突然发倡议书：让世界充满爱再过十几年，或几十年，估计中国的名校都没有人读了startup 工作机会: full-stack, backed, big data, ML (转载Credit Karma内推update 拿到offer,再发20个包子求一切顺利Multiple Job Openings in Chicago Financial Company这算java没学好吗？不刷题，是不是绝对进不了flag？Massachusetts Bans Employers From Asking Applicants About Previous Pay[bssd]谈一下我在美国所见到的两种国男，顺便说一下reference 的问题