桶排序：数组中前K个频率最高的数字
思路：
1.先使用哈希表统计数组中每个数字频率
2.统计完成后，创建一个数组，之前计算的频率作为数组的下标
3.对于出现频率不同的数字集合，存进对应的数组下标
结合代码和每一行的注解理解
//基于桶排序求解「前 K 个高频元素」
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中存在这个key值
map.put(num,map.get(num)+1);//这是如果存在，就这替value，肯定是+1，为了计数
}else{
//不存在就直接加进去
map.put(num,1);
}
}
//桶排序，应该是在这一步将数组的频率从小到大作为下标进行key的填充
//将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
List<Integer>[]list=new List[nums.length+1];
for(int key:map.keySet()){//map.keySet()返回Map集合中所有key组成的Set集合
// 获取出现的次数作为下标
int i=map.get(key);//get(Object key) 返回指定键所映射的值value
if(list[i]==null){
list[i]=new ArrayList();//如果这个下标的对应数组的数值是空的就加进去
}
list[i].add(key);//通过下标把原始的数字放上去，这样数组就完成了，只剩下排序了
}
// 倒序遍历数组获取出现顺序从大到小的排列
for(int i=list.length-1;i>=0&&res.size()<k;i--){//倒序，循环条件，只有加进去的元素的数量小于k，就继续添加，直到等于大于
if(list[i]==null)continue;
res.addAll(list[i]);
}
int[] res1 = res.stream().mapToInt(Integer::valueOf).toArray(); //题目返回的是int[],所以要强制转换
return res1;
}
}
投递美团等公司7个岗位 >
查看14道真题和解析