千万条记录的数组找 Top100，什么算法时间复杂度较低

V2EX = way to explore

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

现在注册

已注册用户请登录

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

时间复杂度最好小于 O(nlogn)

8 条回复 • 2020-07-04 06:10:34 +08:00

Kilerd

2020-06-15 14:35:14 +08:00

限制 nLogN 那就快排一下，取前 100 （反正你也没要求空间复杂度

xupefei

2020-06-15 14:36:41 +08:00 via iPhone

heap sort，复杂度 n log100

Perry

2020-06-15 14:41:51 +08:00 via iPhone

先找到没有排好的 top 100

B1ankCat

2020-06-15 17:02:48 +08:00

按理论来说最小堆就行

takemeaway

2020-06-15 17:12:18 +08:00

O(1)即可

unixeno

2020-06-15 17:18:22 +08:00 via Android

构建一个 100 元素的小顶堆
然后遍历数组，大于堆顶元素的时候就交换，然后调整堆

wangfyyy

2020-06-15 18:22:37 +08:00

看来这不是一道经典的面试题

yishanhe

2020-07-04 06:10:34 +08:00

其实用堆的话，空间复杂度是 O(k) 时间复杂度是 O(nlogk)
这里的 k 就是 100
已经比 O(nlogn) 小了

如果要找比 O(nlogk) 还少的，那么就只能空间换时间了，可以用 bucket sort
时间复杂度 O(n) 空间复杂度也是 O(n)