在这一小节,我们使用优先队列的思路,求解了 topK 问题。再列两道力扣上的相关问题。
使用优先队列的思路,时间复杂度是 O(nlogk) 的,空间复杂度是 O(k) 的。
可能有些同学知道,我们可以使用快速排序算法的思想,在 O(n) 的时间, O(1) 的空间下,同样解决 topK 的问题。(如果对此不了解的同学,请在网上搜索学习一下。)
那么,请大家仔细思考一下:使用优先队列,似乎时间复杂度和空间复杂度都比使用快速排序的思路进行改进要差,那么使用优先队列解决 topK 问题的优势是什么?
(也推荐阅读一下我在力扣上写的这个题解:https://leetcode-cn.com/problems/checking-existence-of-edge-length-limited-paths/solution/jie-zhe-ge-wen-ti-ke-pu-yi-xia-shi-yao-j-pn1b/)