力扣 | 347. 前 K 个高频元素

2023-12-19 22:24:36

leetcode 347 号算法题:前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。

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

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

1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Problem_347_TopKFrequentElements {
    public int [] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num,0) + 1 );
        }
        PriorityQueue<Integer> pq
                = new PriorityQueue<>(k + 1,(a,b) -> count.get(a) - count.get(b));

        for (int num : count.keySet()) {
            pq.add(num);
            if(pq.size() > k) pq.remove();
        }
        int [] res = new int[k];
        int index = 0;
        while (!pq.isEmpty()){
            res[index++] = pq.remove();
        }
        return res;
    }
}

文章来源:https://blog.csdn.net/qq_37247026/article/details/135092259
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。