前K个高频元素，这是一个很有代表性的问题，在实际生活中的应用场景其实也很多，比如微博里每天统计实时热点信息等。
先看下题：
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
这道题的进阶要求时间复杂度要优于O(nlogn)，那一般的快排，归并等就可以抛弃了。
而对于logn这个时间复杂度我们能很快速的联想到二分，二叉搜索树和堆。前两个想了下本场景适用不了。
运用堆
因此我们来推导下堆是否可以小于O(nlogn)？答案是肯定的，堆可以在O(nlogk)(k<n)的时间复杂度下等到结果.
桶排序
那除了堆，我们还有其他办法解决么？当然是有的，那就是桶排序。
思路
我们来理一下为什么可以用堆和桶排序两种实现得到答案。我的推导过程如下，大家可以当做参考，有好的方案也欢迎和我讨论。
首先要统计前k个高频元素，我们必须至少要将整个数组遍历一次。这个我们很快就想到Map去记录每个元素出现的次数，这个在字母异位词那题里面做过。
然后需要去从Map里面的value进行排序，排序后从大到小的前k个元素就是结果。而造成解法差异就是在排序的实现上。
你可以是各种排序，快排，归并，插入，桶，冒泡，希尔，堆排序等，而各种排序的时间复杂度决定了最后的时间复杂度。
然后由于在各个排序里小于进阶要求O(nlogn)的就只有堆排序的O(nlogk)和桶排序的O(n).
具体实现
堆
法一
int[] topK = new int[k];
Map<Integer, Integer> countMap = new HashMap<>();
//第一个为数组值，第二个为出现次数
PriorityQueue<int[]> priQueue = new PriorityQueue<>((o1,o2)->(o2[1]-o1[1]));
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
int value = entry.getKey(), count = entry.getValue();
priQueue.offer(new int[]{value, count});
}
for (int i = 0; i < k; i++) {
topK[i] = priQueue.poll()[0];
}
return topK;
这个是我一开始写的一种错误的写法，应该是初学者比较容易犯的错误。这个解法的时间复杂度是O(nlogn)而不是O(nlogk)，至于为什么，看下一个解法我会说明。而且这里面PriorityQueue的泛型类型用的是int[]，这个写的其实还是有点不优雅的，没必要新开结构去记录，直接用现有的Map.Entry<Integer,Integer>即可。
法二
int[] topK = new int[k];
Map<Integer, Integer> countMap = new HashMap<>();
//第一个为数组值，第二个为出现次数
PriorityQueue<int[]> priQueue = new PriorityQueue<>((o1,o2)->(o1[1]-o2[1]));
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
int value = entry.getKey(), count = entry.getValue();
//始终保持堆里只有k个元素，这样logk速度会快点
if (priQueue.size() < k) {
priQueue.offer(new int[]{value, count});
} else {
if (priQueue.peek()[1] < count) {
priQueue.poll();
priQueue.offer(new int[]{value, count});
}
}
}
for (int i = 0; i < k; i++) {
topK[i] = priQueue.poll()[0];
}
return topK;
法二和法一的区别在于，法一是构建大顶堆，将n个元素都装进堆PriorityQueue中，这样整个建堆的时间复杂度是O(nlogn)，而法二是构建小顶堆，然后保持堆里面的元素始终只有k个，大于k个会先将堆顶元素出堆在将其他元素入堆。
对于在O(nlogk)的复杂度到底用大顶堆还是小顶堆是怎么确定的呢？我是这么记得，如果是要得到前k大的数，那就要构建小顶堆，然后不断将大于堆顶的数放进小顶堆，最后堆里剩下的就是最大的k个数了；反之亦然。
法三
if (nums.length == 0 || nums.length < k) {
return new int[]{};
}
Map<Integer, Integer> numsMap = new HashMap<>();
for (int num : nums) {
numsMap.put(num, numsMap.getOrDefault(num, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> pri = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
for (Map.Entry<Integer, Integer> num : numsMap.entrySet()) {
if (pri.size() < k) {
pri.offer(num);
} else if (pri.peek().getValue() < num.getValue()) {
pri.poll();
pri.offer(num);
}
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = pri.poll().getKey();
}
return res;
法三是Map.Entry<Integer,Integer>实现，这样代码会简洁很多，可读性好很多。
下面发四是从其他地方看到的实现方法，看看和法三有什么不同呢？
我一开始看到也想了一会才发现实现思路。
法四
Map<Integer, Integer> map = new HashMap();
for(int n : nums) {
int freq = map.getOrDefault(n, 0) + 1;
map.put(n, freq);
}
//这里是直接将map的entry做比较，这样就能有多个元素了，不用新建数组或者实体类
Queue<Map.Entry<Integer,Integer>> heap = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
/**
* 这里也是维护一个小根堆，但是这里思路和正常有点区别，正常思路是会在k个元素满之后判断元素是否比堆顶大，然后出堆入堆，
* 这里实现有点不一样，是先入堆，然后在出堆堆顶元素，这里时间复杂度是O(nlog(k+1))，理论上说应该比O(nlogk)慢，
*/
for(Map.Entry<Integer,Integer> entry: map.entrySet()) {
heap.offer(entry);
if(heap.size() > k) {
heap.poll();
}
}
int[] res = new int[k];
for(int i = 0; i < k; i++) {
res[i] = heap.poll().getKey();
}
return res;
这里的时间复杂度严格来说是O(nlog(k+1))，因为堆里会有k+1个元素，当检测到元素大于k会将堆顶最小元素出堆然后在入堆，这样省略了比较过程，但是时间复杂度高了点，在对性能要求不那么严格的时候也可以这种解法。
桶排序
桶排序的思路是会用1-nums.length这么多个桶，然后遍历整个Map，把Map的Entry放进value的桶里，这时候一个桶可能有多个元素，然后依次从大到小将元素取出来即可。
这里我一开始想的比较简单直接用一个数组代替一个桶，这样是不行的，桶可能会有多个元素，会存在覆盖的情况，之后再计数排序的场景可以用数组代替桶。
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
//不能直接用数组记录，因为会存在多个数字出现次数一样，这种用数组会被覆盖
//因此直接在每个数组位置放一个list。
//桶的含义是每个出现次数包含的数字，桶里的元素是多个
//一个桶里会包含所有出现次数为该桶下标的数字
List<Integer>[] tong = new ArrayList[nums.length + 1];
for (Map.Entry<Integer, Integer> num : countMap.entrySet()) {
if (tong[num.getValue()]==null) tong[num.getValue()] = new ArrayList<>();
tong[num.getValue()].add(num.getKey());
}
int[] res = new int[k];
int index = 0;
//因为数组元素赋值是到了nums.length,因此是从nums.length而不是nums.length-1
for (int i = nums.length; i >= 0; i--) {
if (tong[i] == null) continue;
for (int n : tong[i]) {
res[index++] = n;
if (index == k) return res;
}
}
return res;
写在最后
我们在做题的时候不要仅仅追求做出来，而要把所有可能的解法都试试，然后比较优劣，对于一些速度比较慢的解法，看看是否能优化将其效率提高。
有的时候你将一个算法的效率提升了十倍乃至几十倍，那种成就感是空前的！
享受这种过程，你后面写出的有“坏味道”的代码会越来越少。
