欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 347: Top K Frequent Elements

程序员文章站 2022-03-07 19:45:07
...

Leetcode 347: Top K Frequent Elements

题目描述:给定一个非空整数数组,返回数组中k个出现频率最高的元素

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

输出:[1,2]    

解释:由于对输入的元素按出现频率由高到低排序后是 [1,2,3] 返回k=2个元素,则返回值为[1,2]

思路:

       1. HashMap 存储 键值对 :   (k, v) = (元素:元素出现的次数)

       2. 根据HashMap中每个键对应的值进行 建立堆的工作。 可用优先队列实现

注:

    优先队列 基于二叉堆实现的, 二叉堆实际使用数组实现的

package Leetcode.Heap.TopKFrequentElements_347;

import java.util.*;

/**
 * leetcode 247
 */
public class Solution2 {
    public List<Integer> topKFrequent(int[] nums, int k){
        List<Integer> topk_list = new ArrayList<Integer>();
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int i: nums){
            count.put(i, count.getOrDefault(i, 0)+1);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2)->count.get(n1)-count.get(n2));
        for (int i: count.keySet()){
            heap.add(i);
            if (heap.size() > k){
                heap.poll();
            }
        }
        while (!heap.isEmpty()){
            topk_list.add(heap.poll());
        }
        Collections.reverse(topk_list);
        return topk_list;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] nums = {3, 2,2,1,1,1};
        int k = 2;
        List<Integer> list = solution2.topKFrequent(nums, 2);
        System.out.println(list);
    }
}