nyc bloomberg onsite 跪经

larry_cn 发表于 2016-9-14 05:01
keep 10 个元素的 数组的话 time 是 10 ＊ n
用 10 size的 heap的 话 是 n log 10

数组你不会二分查找么？。。。。就相当于一个priority_queue了。

freesam 发表于 2016-9-14 05:06
数组你不会二分查找么？。。。。就相当于一个priority_queue了。

如果 插入一个 元素的话 数组是要 移位的
这个 时间是 数组的大小

补充内容 (2016-9-14 05:09):
要 保持 数组有序的 话

larry_cn 发表于 2016-9-14 05:08
如果 插入一个 元素的话 数组是要 移位的
这个 时间是 数组的大小

用heap的话，你然道不要移位数组？heapify的时候依然要shift down or shift up吧，

freesam 发表于 2016-9-14 05:13
用heap的话，你然道不要移位数组？heapify的时候依然要shift down or shift up吧，

要 不过是 log的 复杂度

比如不适top10 换成 top k的 话
array 就是 O(k)  
heap 的话 是 O(lg k)

larry_cn 发表于 2016-9-14 05:16
要 不过是 log的 复杂度

比如不适top10 换成 top k的 话

恩，当时觉得数组最简单，就直接写了。。

第一题复杂度跪了吧。。。数组移位O(n)啊

oily 发表于 2016-9-14 05:30
第一题复杂度跪了吧。。。数组移位O(n)啊

总的time 没有区别好么？ top 10是constant，你插入是log(n)，我不觉得数组有啥问题，在说你不可能每次都把元数插入最开始处啊，大多数时间不用插入。总的时间是log(n)和heap一样，多一个常数而已。

没有很明白..是有个data stream一直在update， t1时刻a0,a1,...a9 t2时刻a10, a11,..a19 (每个新时刻完全换一批)？
还是t1是 a0, a1,.....a9, t2 是a1, a2,...a10? （每个新时刻dequeuer 1个， 再enqueue 1个）？
问题有些白目...lz谅解

白丁117 发表于 2016-9-14 07:51
没有很明白..是有个data stream一直在update， t1时刻a0,a1,...a9 t2时刻a10, a11,..a19 (每个新时刻完全换 ...

进来一个出去一个，一直有data，随时调用top10

freesam 发表于 2016-9-14 08:02
进来一个出去一个，一直有data，随时调用top10

题目说用array (data length不变)存的？ 谢~