算法题求解,关于排序

2018-06-28 22:41:27 +08:00
 hwdef

在百万级数据中怎么找到最大的 10 个数?

我觉得应该不会用排序,只会用标记,这么大的数据,什么排序也都太慢了。 可能是我想的太简单 不知道大家有什么想法。

3520 次点击
所在节点    算法
15 条回复
linap
2018-06-28 22:55:05 +08:00
一个 10 大小的数组。遍历数据,数据如果大于数组中的最小的数,替换那个数
twistoy
2018-06-28 22:55:44 +08:00
维护一个大小为 10 的大根堆。时间复杂度 O(n)
aaax7676
2018-06-28 22:57:15 +08:00
top k 问题,维护个容量为 k 的堆
sylxjtu
2018-06-28 23:30:25 +08:00
跑 10 遍 nth_element?
neosfung
2018-06-28 23:34:40 +08:00
@twistoy 小根堆
Win78
2018-06-29 00:53:50 +08:00
优先队列
easylee
2018-06-29 01:03:05 +08:00
题目我没有什么好的解决办法,但是搁在实际应用中,我是后台定时排序,然后存储标记,这样一来虽然不能做到实时查询,但是很方便,不会牺牲时间复杂度。
twistoy
2018-06-29 10:36:43 +08:00
@neosfung 取最大的 10 个应该是大根堆吧
neosfung
2018-06-29 10:49:43 +08:00
@twistoy 小根堆,堆顶是前十个最大数中,最小的数。新进来的数和堆顶比较大小,比堆顶大的,就把堆顶换成新进来的数,然后调整堆;否则比堆顶小的,就不管了。
hwdef
2018-06-29 11:46:01 +08:00
@linap 这个方法确实很简单
chashao
2018-06-29 15:37:52 +08:00
@twistoy 我觉得时间复杂度是 O(10lgn)
twistoy
2018-06-30 19:25:15 +08:00
@chashao 怎么可能…
n 个数至少要遍历一遍,至少是 O(n)
chashao
2018-06-30 20:03:05 +08:00
@twistoy 每次建堆不是 O(lgn)么……
twistoy
2018-06-30 21:43:17 +08:00
@chashao 但是堆大小是固定 10 的
Templ1
2018-07-01 07:14:42 +08:00
静态查询-->右转各种堆,各种排序
动态查询-->平衡树

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/466700

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX