在这一小节,我们知道了,我们可以使用优先队列,来求解 topK 问题。这样做,时间复杂度是 O(nlogk) 的,空间复杂度是 O(k) 的。
回忆一下之前学习快速排序算法之后,我曾经提过,其实我们可以基于快速排序的算法进行修改,来设计出一个求解 topK 问题的算法。这个算法时间复杂度是 O(n) 的,空间复杂度是 O(1) 的。
在这里,希望大家对这两种算法实现 top K 问题都有所实践。力扣上有两个问题,大家可以参考:
请大家使用两种方法,解决这两个问题。之后讨论一下:
使用优先队列,似乎时间复杂度和空间复杂度都比使用快速排序的思路进行改进要差,那么使用优先队列解决 topK 问题的优势是什么?