力扣347 前K个高频元素

力扣347 前K个高频元素_第1张图片

    本题是让求前k个高频元素,容易想到按照频率的优先级排序,然后找到前k个。可以使用堆,我们只需要堆的大小是k即可,那这个堆是大根堆还是小根堆呢?如果是大根堆,队首是最大的,如果一个元素出现的次数比队首小,但是比队尾大,这就不好比较;如果是小根堆,队首是最小的,如果一个元素出现的频率比这个队首大,那就说明队首不满足出现次数在前K个要求,所以移出队首,将这个元素加入队列中。所以我们需要按照出现次数,建立一个小根堆。
    我们首先需要定义一个map,将元素及其出现次数都记录下来,然后定义一个优先队列,这个优先队列按照元素次数从小到大进行排序。然后就要开始将map中的元素放进队列中了,在队列中的元素个数还没到达k之前,可以直接将元素放进队列,一旦队列中的元素个数等于k了,那么后来的元素都需要进行判断,如果队首的出现次数比当前元素大,就不用管,如果队首出现的次数比当前元素小,就需要移出队首,然后将当前值加入队列中,重新调整,建立小根堆。这样最后小根堆里面的元素就是出现次数在前K个的元素了。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
//        数组中都一个数表示元素,第二个数表示元素出现的次数,这个堆是按照出现次数从小到大排列的
        PriorityQueue<int[]> queue=new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });

        for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
            int num=entry.getKey(),count=entry.getValue();
            if(queue.size()==k) {
//                如果堆顶的值大于count,说明堆里面的所有值都大于count,如果堆顶的值小于count,那么说明堆顶不符合前k的要求
                if(queue.peek()[1]<count) {
                    queue.poll();
//                    将元素加入队列中,会自己按照出现次数排序
                    queue.offer(new int[]{num, count});
                }
            }
            else {
                queue.offer(new int[]{num,count});
            }
        }
        int[] ret=new int[k];
        for(int i=0;i<k;i++) {
//            poll就是从堆顶中拿出来,因为可以按照任意顺序返回,这块就直接poll就可
            ret[i]=queue.poll()[0];
        }
        return ret;

    }
}

你可能感兴趣的