通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

前 K 个高频元素

228人浏览 / 0人评论 / | 作者:whisper  | 分类: 数据结构-数组  | 标签: 数据结构-数组  | 

作者:whisper

链接:https://www.proprogrammar.com/article/887

声明:请尊重原作者的劳动,如需转载请注明出处


对于top k问题,可以使用优先队列(大顶堆,小顶堆)


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

示例 1:

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

示例 2:

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

JAVA解法

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for(int n: nums){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<Long> queue = new PriorityQueue<Long>((l1, l2) -> l2.compareTo(l1));

        for(int key: map.keySet()){
            queue.offer((map.get(key).longValue() << 32) + key);
        }

        int[] res = new int[k];
        for(int i = 0; i < k; i++){
            res[i] = (int)(queue.poll() & 0xffffffff);
        }

        return res;
    }

使用哈希表+优先队列,哈希表存出现次数,优先队列对次数排序,这里有个技巧是把int型的原数和出现次数同时存在一个long型的数中


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告