[daily question] top k high frequency elements

347. Top k high frequency elements

Given a non empty array of integers, return the elements with the highest frequency before K.

Example 1:

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

Example 2:

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

Tips:

reflection:

Generally, this problem of seeking TOPK often uses heap for operation. Generally speaking, the large top heap is used for the elements with small top k, and the small top heap is used for the elements with large top K. the template is as follows:

//创建堆 默认是小根堆，即每次堆顶元素是最小的 ，
Queue<Integer> pq = new PriorityQueue<>();
//大根堆的创建方式：Queue<Integer> pq = new PriorityQueue<>((v1,v2) -> v2 - v1);

for(int num : arr){
    if(pq.size() < k){
        pq.offer(num); // 堆内元素个数小于 k 的时候，无脑插入
    }else if(num > pq.peek()) // 以据题意进行改变，需要存前k大的数，那么当前数必须大于堆顶才有机会入队
    {
        pq.poll();
        pq.offer(num);
    }
}

In this topic, it is easy to think of the following ideas: