【leetcode】前 K 个高频元素

【leetcode】前 K 个高频元素

题目：

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

示例 1:

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

输入: nums = [1], k = 1
输出: [1]
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

思路：

求频率最高的题目， 第一想法就是要用HashMap，key是每个数字，value是数字出现的次数。
求出每个数字的频率之后，我们想要求出第k高的频率的元素，并且时间复杂度必须优于O(nlog n)，那么该如何求呢？
我们应该想到，堆的时间复杂度正好是O(nlog n)，可以用堆来求。而堆是可以利用优先队列PriorityQueue来求的。
重写compare方法，把频率最高的前k个数字加入queue中， 最后只要把优先队列中的值给弹出，然后再add到list中去就可以了。

java代码：

class Solution {
   public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
 
        Map<Integer, Integer> map = new HashMap();
        for (int i : nums) {
            if (!map.containsKey(i)) {
                map.put(i, 1);
            } else {
                map.put(i, map.get(i) + 1);
            }
        }
 
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });
 
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.add(entry.getKey());
            } else {
                if (entry.getValue() > map.get(queue.peek())) {
                    queue.remove();
                    queue.add(entry.getKey());
                }
            }
        }
 
 
        while (!queue.isEmpty()) {
            res.add(queue.remove());
        }
 
        return res;
    }
}