算法题求解，关于排序

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2369 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

排序

求解

个数

标记

15 条回复 • 2018-07-01 07:14:42 +08:00

linap

2018-06-28 22:55:05 +08:00 via Android

一个 10 大小的数组。遍历数据，数据如果大于数组中的最小的数，替换那个数

twistoy

2018-06-28 22:55:44 +08:00 via Android

维护一个大小为 10 的大根堆。时间复杂度 O(n)

aaax7676

2018-06-28 22:57:15 +08:00 via Android

top k 问题，维护个容量为 k 的堆

sylxjtu

2018-06-28 23:30:25 +08:00 via Android

跑 10 遍 nth_element?

neosfung

2018-06-28 23:34:40 +08:00 via iPhone

@twistoy 小根堆

Win78

2018-06-29 00:53:50 +08:00 via Android

优先队列

easylee

2018-06-29 01:03:05 +08:00 via Android

题目我没有什么好的解决办法，但是搁在实际应用中，我是后台定时排序，然后存储标记，这样一来虽然不能做到实时查询，但是很方便，不会牺牲时间复杂度。

twistoy

2018-06-29 10:36:43 +08:00 via Android

@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 via Android

@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 via Android

@twistoy 每次建堆不是 O(lgn)么……

twistoy

2018-06-30 21:43:17 +08:00

@chashao 但是堆大小是固定 10 的

Templ1

2018-07-01 07:14:42 +08:00 via Android

静态查询-->右转各种堆，各种排序
动态查询-->平衡树