题目：
347. Top K Frequent Elements
解题思路：
Top K问题。给定一个非空的整数数组，返回其中出现频率前k高的元素。
看过题解，发现总的来说有两个思路：
第一个思路是使用桶排序。首先创建一个Map记录数组中每个元素的频率；然后创建一个数组将元素按照频率升序存放在List中;定义i来接收每个元素的频率，并且元素按照出现频率作为数组下标存储;最后对数组逆向求出前k个高频的元素，放入结果集ans。
详见
第二个思路是使用堆，维护一个大小为K的小根堆，堆按数字出现频率从小到大排列。
利用小根堆的特性，把前K个高频元素保留起来，再依次输出。
详见
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71桶排序：
Java:
public int[] topKFrequent(int[] nums,int k){
List<Integer> ans = new ArrayList<>();
if(nums == null) return null;
//记录每个元素的频率
Map<Integer,Integer> map = new HashMap<>();
for(int n : nums){
map.put(n,map.getOrDefault(n,0) + 1);
//Map.getOrDefault(Object key, V defaultValue);
//判断map中是否包含key值, 包含返回该key值对应的value值;否则返回defaultValue值.
}
//按照map中元素的频率来创建数组，高频率的元素位于数组最后边
//这步是桶排序的体现
List<Integer>[] tmp = new List[nums.length + 1];
for(int key : map.keySet()){
//定义i来接收每个元素的频率值
int i = map.get(key);
if(tmp[i] == null)
tmp[i] = new ArrayList();
//将对应频率的元素放入以频率为下标的数组中
tmp[i].add(key);
}
//逆向找出前k高频率的元素
for(int i = tmp.length - 1;i>=0 && ans.size()< k;--i){
if(tmp[i] == null)
continue;
//将当前频率下的元素放入结果集ans中
ans.addAll(tmp[i]);
//addAll()具体用法
//https://www.breakyizhan.com/java/4561.html
}
//将List<Integer>转换成int[]
return ans.stream().mapToInt(Integer::valueOf).toArray();
//Lambda表达式中的方法引用
小根堆：
public int[] topKFrequent(int[] nums,int k){
//记录每个数出现的概率
HashMap<Integer,Integer> count = new HashMap<>();
for(int n : nums){
count.put(n,count.getOrDefault(n,0) + 1);
}
//维护一个长度为k的小顶堆，以概率从小到大排列
PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1,n2)-> count.get(n1) - count.get(n2));
//接口的lambda表达式写法
//Comparator接口参考网址：
//https://blog.csdn.net/qq_35008612/article/details/80956990
//https://www.cnblogs.com/mengzj233/p/9816289.html
//维护k长度的优先队列
for(int n : count.keySet()){
heap.add(n);
if(heap.size() > k)
heap.poll();
}
//输出小顶堆中内容，注意还需要反转一次保证频率最大的在前
List<Integer> top_k = new LinkedList();
while(!heap.isEmpty())
top_k.add(heap.poll());
Collections.reverse(top_k);
return top_k.stream().mapToInt(Integer::valueOf).toArray();
}
