时间复杂度最好小于 O(nlogn)
This topic created in 2332 days ago, the information mentioned may be changed or developed.
 |
KilerdJun 15, 2020
1
限制 nLogN 那就快排一下，取前 100 （反正你也没要求空间复杂度
|
 |
xupefeiJun 15, 2020 via iPhone
2
heap sort，复杂度 n log100
|
 |
PerryJun 15, 2020 via iPhone
3
先找到没有排好的 top 100
|
 |
B1ankCatJun 15, 2020
4
按理论来说最小堆就行
|
 |
takemeawayJun 15, 2020
5
O(1)即可
|
 |
unixenoJun 15, 2020 via Android
6
构建一个 100 元素的小顶堆
然后遍历数组，大于堆顶元素的时候就交换，然后调整堆 |
 |
7
看来这不是一道经典的面试题
|
 |
yishanheJul 4, 2020
8
其实用堆的话 ，空间复杂度 是 O(k) 时间复杂度是 O(nlogk)
这里的 k 就是 100 已经比 O(nlogn) 小了 如果要找比 O(nlogk) 还少的，那么就只能空间换时间了，可以用 bucket sort 时间复杂度 O(n) 空间复杂度 也是 O(n) |
Select Language