-
Notifications
You must be signed in to change notification settings - Fork 0
/
Q347TopKFrequentElements.java
103 lines (93 loc) · 3.05 KB
/
Q347TopKFrequentElements.java
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.util.*;
/**
* @author ahscuml
* @date 2019/1/2
* @time 17:05
*/
public class Q347TopKFrequentElements {
/**
* 测试函数
*/
public static void main(String[] args) {
int[] nums = {1, 2, 2, 3, 3, 3};
int k = 2;
System.out.println(topKFrequent(nums, k));
}
/**
* 使用桶排序来做这件事情
* 利用HashMap统计频次
* 利用List的数组存储结果
*/
public static List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList();
HashMap<Integer, Integer> map = new HashMap();
// 将数组存储到HashMap中统计频率
for (int i : nums) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
// 遍历存有频率的HashMap,利用存有list的数组bucket 按照频率将元素存储到bucket里
// 如何遍历HashMap也是一个重点
List<Integer>[] bucket = new List[nums.length + 1];
for (int i : map.keySet()) {
int fre = map.get(i);
if (bucket[fre] == null) {
bucket[fre] = new LinkedList();
}
bucket[fre].add(i);
}
// 从bucket中从大到小取出结果
for (int i = bucket.length - 1; i > 0 && k > 0; i--) {
if (bucket[i] != null) {
res.addAll(bucket[i]);
k -= bucket[i].size();
}
}
return res;
}
/**
* 使用堆来完成任务,也就是PriorityQueue
* */
public static List<Integer> topKFrequentII(int[] nums, int k) {
// 利用HahsMap来存储频次
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}
// 优先队列的使用
PriorityQueue<Map.Entry<Integer, Integer>> maxHeap =
new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
maxHeap.add(entry);
}
List<Integer> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, Integer> entry = maxHeap.poll();
res.add(entry.getKey());
}
return res;
}
/**
* 使用TreeMap来完成这个任务
* */
public static List<Integer> topKFrequentIII(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}
TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
for(int num : map.keySet()){
int freq = map.get(num);
if(!freqMap.containsKey(freq)){
freqMap.put(freq, new LinkedList<>());
}
freqMap.get(freq).add(num);
}
// 对于TreeMap的使用
List<Integer> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
res.addAll(entry.getValue());
}
return res;
}
}