LeetCode 347. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Note:
- You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
- Your algorithm’s time complexity must be better than O( n log n ), where n is the array’s size.
分析
要统计数组中出现频率前k高的数字。从数字到频率，考虑用HashMap来建立映射。然后再处理前k高的问题。
题解
首先遍历一遍数组，统计各数字出现次数，确定使用HashMap几乎没什么争议。
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums) {
if(map.containsKey(num)) {
map.compute(num, (key, v) -> {
++v;
return v;
});
}else {
map.put(num, 1);
}
}
要取其中出现次数（value）前k高的元素，一定需要进行排序，有两种方法可供选择
题解、堆排序
看到第k大\小马上想到的方法，Java实现起来也非常方便。因为前面已经用了Map，这里不需要再引入新的数据结构，直接用Map.Entry建堆就可以了。前k大，所以建一个大顶堆，全部加进去之后poll出k个来就行了。
时间复杂度$O(n\log n)$
int[] res = new int[k];
//统计出现次数
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums) {
if(map.containsKey(num)) {
map.compute(num, (key, v) -> {
++v;
return v;
});
}else {
map.put(num, 1);
}
}
//建堆
PriorityQueue<Map.Entry<Integer, Integer>> maxHeap =
new PriorityQueue<>(Comparator.comparingInt(o -> -o.getValue()));
maxHeap.addAll(map.entrySet());
//输出
for(int i = 0; i < k; ++i)
res[i] = maxHeap.poll().getKey();
return res;
题解、计数（桶）排序
我们知道桶排序时间复杂度是$O(n)$，要能派上用场肯定比堆排序好，那用什么建桶呢？用输入数组中的数字不适合直接建桶，因为我们并不关心其大小，需要关心的是出现次数。
长度为nums.length的数组，那出现次数最多也就是nums.length，我们可以跟据出现次数来建桶，每个桶中的数出现次数都相同，这其实就像考生排名次，分数（出现次数）越大的名词数越低（在输出数组中下标越小），那这其实就是一种特殊的桶排序——计数排序，按出现次数进行计数。
int[] res = new int[k];
int resIdx = 0;
//统计出现次数
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums) {
if(map.containsKey(num)) {
map.compute(num, (key, v) -> {
++v;
return v;
});
}else {
map.put(num, 1);
}
}
//统计每个桶中数据量，即出现次数相同的数字个数，按出现次数存入reference[]中
//顺便统计一下最大的出现次数
Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
int maxOccurrence = 1;
int[] reference = new int[nums.length + 1];
for(Map.Entry<Integer, Integer> entry : entrySet) {
reference[entry.getValue()]++;
if(maxOccurrence < entry.getValue())
maxOccurrence = entry.getValue();
}
//将数组每一元素更新为包括自身在内之前所有元素之和，形成索引数组
for(int i = 1; i <= maxOccurrence; ++i) {
reference[i] += reference[i - 1];
}
//计数排序不可避免的是从小开始，我们要找的是前k大，
//也就是在最终排序输出数组中位置大于(entrySet.size()-k-1)的部分
k = entrySet.size() - k - 1;
for(Map.Entry<Integer, Integer> entry : entrySet) {
//同一次数，出现多次的，递减以防止重叠
reference[entry.getValue()]--;
if(reference[entry.getValue()] > k)
res[resIdx++] = entry.getKey();
}
return res;
Entry<Integer, Integer>中的键(Key)是我们最终要输出的原数字，而值(Value)是我们关心的出现次数，如果我们有建立一个从出现次数到原数字的“反向映射”，那也可以对出现次数数组（valueSet）进行进行遍历排序，然后输出对应的键。
但是实际上，Java提供的Entry已经足够好用，建立反向映射需要大量额外空间，但却不能保证带来时间效率的提升，所以直接对Map.EntrySet进行遍历，输出排序结果就行了，这一部分的时间复杂度实际已经低于$O(n)$，是$O(j)$（$j$为nums[]中不同元素个数）。
总而言之，桶排序的时间复杂度为$O(n)$
最后，我们知道由于伪泛型设计，Java中的HashMap既没有STL中的Map效率高，用起来也不方便，因此，大部分情况下可以考虑一下用数组代替。然而这道题数字没有给范围，从负数到最大10^5都有可能，用数组不方便，因此作罢。