Top K类型题（bucket sort, inplace quick sort and Comparator）
Top K类型题（bucket sort, inplace quick sort and Comparator）
基本类top k
今天总结了一下Top K这种类型的题目的做法，总的来说一般有三种做法：
- 最简单的就是进行sorting，然后取前K个，时间复杂度是O(nlogn)
- 第二种做法是使用Priority Queue(最小堆)，Priority Queue只存储目前遇到的最大的K个元素，每次堆中元素大于K的时候我们就poll出目前最小的元素(已经有K个比他大，他肯定不是结果了)，那么时间复杂度是O(nlogk)
- 最复杂的做法是使用Quick Select，由于我们只关心前K个元素，所以相当于对于Quick Sort，我们每次partition只取一半，所以时间复杂度只有O(n)。(T(n) = T(n/2) + n)
注意：当我们是求某一个频率的前K个元素的时候，我们可以不用复杂的Quick Select，而是使用简单的Bucket sort。这里能够使用bucket sort的原因在于元素的frequency肯定不大于数组的长度，也就是说有一个固定的边界。我们知道bucket sort能够使用的条件就是有固定的边界。而求取前K个最大的元素，由于元素的大小是没有边界的，所以无法使用bucket sort，我们只能用Quick Select。