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

2020-06-15 14:31:50 +08:00
 wangfyyy

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

1998 次点击
所在节点    算法
8 条回复
Kilerd
2020-06-15 14:35:14 +08:00
限制 nLogN 那就快排一下，取前 100 （反正你也没要求空间复杂度
xupefei
2020-06-15 14:36:41 +08:00
heap sort，复杂度 n log100
Perry
2020-06-15 14:41:51 +08:00
先找到没有排好的 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
构建一个 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)

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

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

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

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

© 2021 V2EX