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 的大作中提到】
: 不对
相关阅读
请教:OPT期间H1B已经approve出境(automatic revalidation)大家有没有人办OPT的时候是E-File的口头offer处理了一个月还没结果，怎么回事？中签的mail寄丢了怎么办Amex Blue Cash preferred 6%现金回扣+$150bonus超市专用信用卡老生长谈的h1b transfer问题，希望得到准确解答(包子帖)VSC Non-PP ADV批了请问BST里怎么处理“等于”的情况？Amex SPG卡送25K points 免费送500刀现金 最佳酒店卡Amazon TRMS is hiring a research scientist请问工作的start date是自己定的么？2條經典 design 問題Google内部推荐这是说h1b申请通过了吗？有没有pp 通过但还没收到official approval的？紧急求助： H4 转 H1B有人看这本书吗 Elements of Programming Interviews二爷又销声匿迹了纽约7万5能活吗google电面一周了