时间复杂度最好小于 O(nlogn)
1
Kilerd 2020-06-15 14:35:14 +08:00
限制 nLogN 那就快排一下,取前 100 (反正你也没要求空间复杂度
|
2
xupefei 2020-06-15 14:36:41 +08:00 via iPhone
heap sort,复杂度 n log100
|
3
Perry 2020-06-15 14:41:51 +08:00 via iPhone
先找到没有排好的 top 100
|
4
B1ankCat 2020-06-15 17:02:48 +08:00
按理论来说最小堆就行
|
5
takemeaway 2020-06-15 17:12:18 +08:00
O(1)即可
|
6
unixeno 2020-06-15 17:18:22 +08:00 via Android
构建一个 100 元素的小顶堆
然后遍历数组,大于堆顶元素的时候就交换,然后调整堆 |
7
wangfyyy OP 看来这不是一道经典的面试题
|
8
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) |