347.前 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 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-elements

思路：

  1. 先用map进行统计
  2. 创一个最小堆，容量为k，遍历map
  3. 将堆输出即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //用map统计，然后堆
        HashMap<Integer, Integer> map = new HashMap();
        for(int num:nums){
            if(map.containsKey(num))
                map.put(num,map.get(num)+1);
            else
                map.put(num,1);
        }
        //下边用优先队列存储，遍历map
        PriorityQueue<Integer> queue = 
                        new PriorityQueue<>((n1,n2)->map.get(n1)-map.get(n2));
        for(Integer key:map.keySet()){
            if(queue.size()<k)
                queue.add(key);
            else if(map.get(key)>map.get(queue.peek())){
                queue.remove();
                queue.add(key);
            }
        }
        //输出堆中元素，就是频率最大的
        int[] res = new int[queue.size()];
        for(int i=0;i<res.length;i++){
            res[i] = queue.remove();
        }
        return res;
    }
}