前k个高频元素

问题陈述

给定一个非空的整数数组，返回其中出现频率前 k 个高频元素。

算法实现

先使用哈希表统计元素及其出现频率，然后基于桶排序的思想获得频率排序，最后遍历得到前k个高频元素。

public class FrequentKElements {
    public List<Integer> 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,1);
            }else{
                map.put(num,map.get(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数组获取出现顺序从大到小的排列
        for(int i=list.length-1;i>=0&&res.size()<k;i--){
            if(list[i]==null) continue;
            res.addAll(list[i]);
        }
        return res;
    }
    public static void main(String[] args){
        int[] nums={1,1,1,2,2,3};
        FrequentKElements frequentKElements=new FrequentKElements();
        System.out.println(frequentKElements.topKFrequent(nums,2));
    }
}