思路：方法1：这道题最开始能想到的方法就是堆，因为是要输出前K个高频元素，我自然想到了大顶堆，堆中保存一个个2元数组，即数字和其出现的频率，按照其频率大小排序，用到了lambda表达式：
class Solution {//求前 k 大，用小根堆，求前 k 小，用大根堆。 public int[] topKFrequent(int[] nums, int k) { PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1,o2)->(o2[1]-o1[1]));//这是大顶堆，复杂度是 nlogn Map<Integer,Integer> map = new HashMap<>(); for(int i:nums){ map.put(i,map.getOrDefault(i,0)+1); } for(int i:map.keySet()){ queue.add(new int[]{i,map.get(i)}); } int[] res = new int[k]; for(int i=0;i<k;i++){ res[i] = queue.poll()[0]; } return res; } }方法2：但是这样的话，时间复杂度就刚好为O(nlogn)，我能不能再让时间复杂度更小呢？由于只用输出前K个高频元素，那么我们的堆中是不是就可以只保存K个元素呢？自然就会想到小顶堆，因为小的元素再堆顶，直接poll出来即可，遍历所有的元素后，堆中自然就只有K个最大元素了：
class Solution {//求前 k 大，用小根堆，求前 k 小，用大根堆。 public int[] topKFrequent(int[] nums, int k) { PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1,o2)->(o1[1]-o2[1]));//这是小顶堆，复杂度是 nlogK Map<Integer,Integer> map = new HashMap<>(); for(int i:nums){ map.put(i,map.getOrDefault(i,0)+1); } int n = 0; for(int i:map.keySet()){ //if(n == k) queue.poll(); queue.add(new int[]{i,map.get(i)}); n++; if(n > k) queue.poll(); } int[] res = new int[k]; int p = 0; while(!queue.isEmpty()){ res[p++] = queue.poll()[0]; } return res; } }通过这两种方法，我们可以得出一个结论：//求前 k 大，用小根堆，求前 k 小，用大根堆。 方法3：为了进一步降低时间复杂度，桶排序是个更好的选择（牺牲空间复杂度换取时间复杂度），第i个桶表示出现频率为i的元素，当然频率相同的元素可能并不只有一个，所以，每个桶中存放一个链表（因为链表是可变长度的），所有元素都存放在桶中后，我们就可以愉快的从后往前遍历啦，res数组填满K个元素即为我们的最终答案啦~~(●’◡’●)
class Solution { public int[] topKFrequent(int[] nums, int k) { ArrayList<Integer>[] buckets = new ArrayList[nums.length+1]; Map<Integer,Integer> map = new HashMap<>(); for(int i:nums){ map.put(i,map.getOrDefault(i,0)+1); } for(int i:map.keySet()){ if(buckets[map.get(i)] == null){ buckets[map.get(i)] = new ArrayList<>(); } buckets[map.get(i)].add(i); } int[] res = new int[k]; int p = 0; for(int i = buckets.length-1;i>=0;i--){ //if(p == k) return res; if(buckets[i] == null) continue;//初始化为null int size = buckets[i].size(); while(size>0){ res[p] = buckets[i].get(size-1); p++; if(p == k) return res; size--; } } return res; } }以上就是三种解法啦，涉及对堆以及桶排序的比较经典的题。注意题目中“数组中前 k 个高频元素的集合是唯一的。“因此 while(size>0)中无需有if(p == k) return res 的判断。
