347. 前 K 个高频元素
347. 前 K 个高频元素
解法一：粗暴排序法
最简单粗暴的思路就是 使用排序算法对元素按照频率由高到低进行排序，然后再取前 k 个元素。可以发现，使用常规的诸如 冒泡、选择、甚至快速排序都是不满足题目要求，它们的时间复杂度都是大于或者等于 O(nlogn)，而题目要求算法的时间复杂度必须优于 O(nlogn)。
复杂度分析
时间复杂度：O(nlogn)，n 表示数组长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；接着，排序算法时间复杂度为 O(nlogn)；因此整体时间复杂度为 O(nlogn)。
空间复杂度：O(n)，最极端的情况下（每个元素都不同），用于存储元素及其频率的 Map 需要存储 n 个键值对。
作者：MisterBooo
链接：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/leetcode-di-347-hao-wen-ti-qian-k-ge-gao-pin-yuan-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二：最小堆
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
HashMap<Integer, Integer> map = new HashMap();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}//map.put(num, map.getOrDefault(num, 0) + 1);
}
// 遍历map，用最小堆保存频率最大的k个元素
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return map.get(a) - map.get(b);
}
});
for (Integer key : map.keySet()) {
if (pq.size() < k) {
pq.add(key);
} else if (map.get(key) > map.get(pq.peek())) {
pq.remove();
pq.add(key);
}
}
// 取出最小堆中的元素
List<Integer> res = new ArrayList<>();
while (!pq.isEmpty()) {
res.add(pq.remove());
}
int[] ret = res.stream().mapToInt(i -> Integer.valueOf(i)).toArray();
return ret;
}
}
解法三：桶排序法
class Solution {
public int[] topKFrequent(int[] nums, int k) {
List<Integer> res = new ArrayList<>();
// 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
HashMap<Integer, Integer> map = new HashMap();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}//map.put(num, map.getOrDefault(num, 0) + 1);
}
//桶排序
//将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
List<Integer>[] list = new List[nums.length + 1];
for (int key : map.keySet()) {
//获取出现的次数作为下标
int i = map.get(key);
if(list[i] == null) {
list[i] = new ArrayList();
}
list[i].add(key);
}
//倒序遍历数组获取出现顺序从大到小的排列
for (int i = list.length - 1; i >= 0 && res.size() < k; i--) {
if (list[i] == null) {
continue;
}
res.addAll(list[i]);
}
int[] ret = res.stream().mapToInt(i -> Integer.valueOf(i)).toArray();
return ret;
}
}