题目描述

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

示例：

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

思路

  1. 这道题是标准的topK问题，需要建立一个小根堆。
  2. 可以先遍历一遍数组，使用一个map存储每个元素出现的次数。
  3. 使用java原生的优先级队列存放Entry,若size大于k，将队首元素出队即可。

Java代码实现

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            numMap.put(nums[i],numMap.getOrDefault(nums[i],0)+1);
        }

        PriorityQueue<Map.Entry<Integer,Integer>> priorityQueue = new PriorityQueue<>(k,(o1,o2)->(o1.getValue()-o2.getValue()));

        Set<Map.Entry<Integer, Integer>> entries = numMap.entrySet();

        for (Map.Entry<Integer,Integer> entry:entries) {
            priorityQueue.add(entry);
            if(priorityQueue.size()>k){
                priorityQueue.poll();
            }
        }

        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < k; i++) {
            res.add(priorityQueue.poll().getKey());
        }
        return res;
    }
}