设置若干个桶,每个桶存储出现频率相同的数。桶的下标表示数出现的频率,即第 i 个桶中存储的数出现的频率为 i。
把数都放到桶之后,从后向前遍历桶,最先得到的 k 个数就是出现频率最多的的 k 个数。
首先依旧使用哈希表统计频率,统计完成后,创建一个数组,将频率作为数组下标,对于出现频率不同的数字集合,存入对应的数组下标即可。
import java.util.*; class Solution { public List<Integer> 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); } } //桶排序 //将频率作为数组下标,对于出现频率不同的数字集合,存入对应的数组下标 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); } List<Integer> res = new ArrayList<>(); //倒序遍历数组获取出现顺序从大到小的排列 for(int i = list.length - 1; i >= 0 && res.size() < k; i--) { if(list[i] == null) continue; res.addAll(list[i]); } return res; } }