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

输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]

方法一：堆排序

思路：先用一个HashMap存储每个数字及其对应的出现次数，并建立一个PriorityQueue用于存储元素并进行排序，之后遍历整个HashMap，当PriorityQueue中元素不满k个的时候直接将元素与其出现次数加入PriorityQueue，当其中元素已有k个且当前元素出现次数大于PriorityQueue中最小的出现次数的时候从PriorityQueue中取出出现次数最少的元素（因为PriorityQueue已被排序，故直接执行poll操作即可），并将当前元素及其出现次数加入PriorityQueue，遍历完成后出现次数前k大的元素已被存储在PriorityQueue中，之后利用PriorityQueue创建答案数组即可。

public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map=new HashMap();
        int[] ans=new int[k];
        for(int i=0;i<nums.length;i++)
        {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        PriorityQueue<int[]>que=new PriorityQueue(new Comparator<int[]>(){
            public int compare(int m[],int n[]){
                return m[1]-n[1];
            }
        });

        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(que.size()==k){
                if(entry.getValue()>que.peek()[1])
                {
                    que.poll();
                    que.offer(new int[]{entry.getKey(),entry.getValue()});
                }
            }else{
                que.offer(new int[]{entry.getKey(),entry.getValue()});
            }
        }

        for(int i=0;i<k;++i){
            ans[i]=que.poll()[0];
        }

        return ans;
    }

方法二：桶排序

新建hashmap的同时可以得到最大出现次数maxtimes，我们新建一个长度为maxtimes+1的arraylist数组buckets，buckets[i[用于存储出现次数为i的元素，随后从后先前遍历buckets，依次将其中元素加入ans数组，当加入元素数母等于k时结束遍历，此时前k大的元素已被加入数组。

public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map=new HashMap();
        int[] ans=new int[k];
        int index=0;
        int maxtimes=0;
        for(int i=0;i<nums.length;i++)
        {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            maxtimes=Math.max(maxtimes,map.get(nums[i]));
        }
        ArrayList<Integer>[] buckets=new ArrayList[maxtimes+1];
        for(int i=0;i<maxtimes+1;i++)
           buckets[i]=new ArrayList();
        map.forEach((k,v)->{
        });
        map.forEach((num, freq) -> {
            buckets[freq].add(num);
        });
        for(int i=maxtimes;i>=1&&index<k;i--){
            for(int j:buckets[i]){
                ans[index++]=j;
                if(index==k)
                   break;
            }
        }
        return ans;
    }