[经典] 在未排序数组中返回topK大的数

时间:2022-11-30 06:46:30

解法一,排序

先从大到小快排,然后扫前K个返回

时间复杂度:O(NlogN),空间复杂度O(1)

解法二,优先队列

前K个放入优先队列中,与最小堆顶元素比较大小,若大于则删除堆顶并插入;否则跳过

时间复杂度:O(NlogK),空间复杂度O(K)

解法三,堆调整

先将数组直接用完全二叉树存储,复杂度O(N);然后对树进行堆调整,调整为最大堆,复杂度不超过O(2N)(对每一层的操作总次数进行分析);最后弹出K个堆顶元素,复杂度不超过O(KlogN)。由于K比N小得多,复杂度为O(N)

时间复杂度:O(N),空间复杂度也是O(N)