算法题求解，关于排序

2018 年 6 月 28 日
 hwdef

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

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

4791 次点击
所在节点    算法
15 条回复
linap
2018 年 6 月 28 日
一个 10 大小的数组。遍历数据，数据如果大于数组中的最小的数，替换那个数
twistoy
2018 年 6 月 28 日
维护一个大小为 10 的大根堆。时间复杂度 O(n)
aaax7676
2018 年 6 月 28 日
top k 问题，维护个容量为 k 的堆
sylxjtu
2018 年 6 月 28 日
跑 10 遍 nth_element?
neosfung
2018 年 6 月 28 日
@twistoy 小根堆
Win78
2018 年 6 月 29 日
优先队列
easylee
2018 年 6 月 29 日
题目我没有什么好的解决办法，但是搁在实际应用中，我是后台定时排序，然后存储标记，这样一来虽然不能做到实时查询，但是很方便，不会牺牲时间复杂度。
twistoy
2018 年 6 月 29 日
@neosfung 取最大的 10 个应该是大根堆吧
neosfung
2018 年 6 月 29 日
@twistoy 小根堆，堆顶是前十个最大数中，最小的数。新进来的数和堆顶比较大小，比堆顶大的，就把堆顶换成新进来的数，然后调整堆；否则比堆顶小的，就不管了。
hwdef
2018 年 6 月 29 日
@linap 这个方法确实很简单
chashao
2018 年 6 月 29 日
@twistoy 我觉得时间复杂度是 O(10lgn)
twistoy
2018 年 6 月 30 日
@chashao 怎么可能…
n 个数至少要遍历一遍，至少是 O(n)
chashao
2018 年 6 月 30 日
@twistoy 每次建堆不是 O(lgn)么……
twistoy
2018 年 6 月 30 日
@chashao 但是堆大小是固定 10 的
Templ1
2018 年 7 月 1 日
静态查询-->右转各种堆，各种排序
动态查询-->平衡树

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

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

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

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

© 2021 V2EX