2022-02-13 (347. Top k high frequency elements)

My most simple idea is to traverse , Get values and times map, Right again map Sort the heap by the number of times in , Or you can line up quickly k Large number . The official answer is the same as I thought .

But I see the following bucket sorting , In fact, it is the idea of exchanging space for time

class Solution {
    
    public int[] topKFrequent(int[] nums, int k) {
    
        int[] result=new 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);
            }
        }
        // Bucket sort 
        // Take the frequency as the array subscript , For a set of numbers with different frequencies , Store the corresponding array subscript 
        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);
        }
        int count=0;
        for(int i=list.length-1;i>=0&&count<k;i--){
    
            if(list[i]==null)continue;
            for(Integer n:list[i]){
    
                result[count++]=n;
            }
        }
        
        return result;
    }
}