LeetCode347.前K个高频元素-526互联

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例

提交的代码

你被骗了，我没做出来，能想到的方法时间复杂度是nlogn，还不如不写，想到小顶堆了，但是Java这里我不知道怎么实现:(

学习到的东西

经典使用堆实现，但是个人的Java基础不太好，不会实现堆，是能去找博文看看了，顺便看了下大佬的实现，我是废物。。。
PriorityQueue()这个类是优先级队列也就是堆的实现类，基本方法和队列很像，poll(),peek(),offer()，isEmpty(),size()等。
至于小顶堆查找一个集合中的top k元素，就不多赘述了，大家都会。直接上最后的代码：

import java.util.PriorityQueue;
import java.util.Map;
import java.util.HashMap;
class Solution {
    //小顶堆实现前K个高频元素
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        //用PriorityQueue来实现堆
        PriorityQueue<int[]> heap=new PriorityQueue<>(k,(element1,element2)->element1[1]-element2[1]);
        //生命结果数组
        int[] result=new int[k];
        int count=0;
        //用Map统计每个数字出现的频度
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        //统计前K个高频的元素
        Set<Map.Entry<Integer,Integer>> entrySet=map.entrySet();
        for(Map.Entry<Integer,Integer> entry:entrySet){
            //堆小于k的时候直接放入
            if(heap.size()<k){
                heap.offer(new int[]{entry.getKey(),entry.getValue()});
            }else{
                //堆顶出堆，新元素如堆尾部，然后重新调整堆
                if(entry.getValue()>heap.peek()[1]){
                    heap.poll();
                    heap.offer(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        //将堆中的元素都放入结果队列中
        while(!heap.isEmpty()){
            result[count++]=heap.poll()[0];
        }
        return result;
    }
}