首页 > 其他分享 >LeetCode347.前K个高频元素

LeetCode347.前K个高频元素

时间:2023-11-02 19:58:08浏览次数:36  
标签:Map int 元素 LeetCode347 PriorityQueue heap new 高频

题目描述

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

示例

image

提交的代码

你被骗了,我没做出来,能想到的方法时间复杂度是nlogn,还不如不写,想到小顶堆了,但是Java这里我不知道怎么实现:(

学习到的东西

经典使用堆实现,但是个人的Java基础不太好,不会实现堆,是能去找博文看看了,顺便看了下大佬的实现,我是废物。。。
PriorityQueue()这个类是优先级队列也就是堆的实现类,基本方法和队列很像,poll(),peek(),offer(),isEmpty(),size()等。
至于小顶堆查找一个集合中的top k元素,就不多赘述了,大家都会。直接上最后的代码:

import java.util.PriorityQueue;
import java.util.Map;
import java.util.HashMap;
class Solution {
    //小顶堆实现前K个高频元素
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        //用PriorityQueue来实现堆
        PriorityQueue<int[]> heap=new PriorityQueue<>(k,(element1,element2)->element1[1]-element2[1]);
        //生命结果数组
        int[] result=new int[k];
        int count=0;
        //用Map统计每个数字出现的频度
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        //统计前K个高频的元素
        Set<Map.Entry<Integer,Integer>> entrySet=map.entrySet();
        for(Map.Entry<Integer,Integer> entry:entrySet){
            //堆小于k的时候直接放入
            if(heap.size()<k){
                heap.offer(new int[]{entry.getKey(),entry.getValue()});
            }else{
                //堆顶出堆,新元素如堆尾部,然后重新调整堆
                if(entry.getValue()>heap.peek()[1]){
                    heap.poll();
                    heap.offer(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        //将堆中的元素都放入结果队列中
        while(!heap.isEmpty()){
            result[count++]=heap.poll()[0];
        }
        return result;
    }
}

标签:Map,int,元素,LeetCode347,PriorityQueue,heap,new,高频
From: https://www.cnblogs.com/whitePuPigeon/p/17806147.html

相关文章

  • 块级元素与行内元素
    一、向下上复制快捷键altshitf向下箭头或者向下箭头二、代码 网页效果  三、总结 ......
  • 面试高频题:你如何知道HashMap正在进行扩容操作?
    亲爱的小伙伴们,大家好!我是小米,一个热爱技术分享的小编。今天,我们将一起来探讨一个程序员们在日常工作中常常遇到的问题——如何知道HashMap正在扩容。HashMap,作为Java中最常用的数据结构之一,经常在我们的代码中扮演着关键的角色。了解HashMap的工作原理,特别是它的扩容机制,可以帮助......
  • DC电源模块去除输出电源中的高频噪声及杂波
    BOSHIDADC电源模块去除输出电源中的高频噪声及杂波DC电源模块是电路中常用的部件,用于提供电子元器件的工作电源。然而,在使用DC电源模块的过程中,往往会出现一些问题,比如输出电源中产生的高频噪声和杂波。这些问题不仅会影响电路的稳定运行,还会影响到元器件的寿命,因此需要采取措施......
  • 【算法题】2817. 限制条件下元素之间的最小绝对差
    题目:给你一个下标从0开始的整数数组nums和一个整数x。请你找到数组中下标距离至少为x的两个元素的差值绝对值的最小值。换言之,请你找到两个下标i和j,满足abs(i-j)>=x且abs(nums[i]-nums[j])的值最小。请你返回一个整数,表示下标距离至少为x的两个元素之......
  • 如何检测元素外部的点击?
    内容来自DOChttps://q.houxu6.top/?s=如何检测元素外部的点击?我有一些HTML菜单,当用户点击这些菜单的头部时,我会完全显示它们。我希望在用户点击菜单区域外时隐藏这些元素。这是否可以通过jQuery实现?$("#menuscontainer").clickOutsideThisElement(function(){//隐藏......
  • 排序(按照第一元素)
    按照元素的第一顺序排序//maybe贪心会用到structty{ intx,y;}a[N];boolcmp(tya,tyb){ if(a.x<b.x)returntrue; returnfalse;}intmain(){ intn; cin>>n; for(inti=1;i<=n;i++) { cin>>a[i].x>>a[i].y; } sort(a+......
  • 【算法题】2909. 元素和最小的山形三元组 II
    题目:给你一个下标从0开始的整数数组nums。如果下标三元组(i,j,k)满足下述全部条件,则认为它是一个山形三元组:i<j<knums[i]<nums[j]且nums[k]<nums[j]请你找出nums中元素和最小的山形三元组,并返回其元素和。如果不存在满足条件的三元组,返回-1。示例1:......
  • 【java基础-实战3】list遍历时删除元素的方法
    在实际的业务开发中,容器的遍历可以说是非常非常常见的场景了,遍历删除呢,用的机会也比较多,那么有哪几种删除元素的方法呢?你用对了吗~本文循序渐进,先说几种容易出问题的方法,再引出几种比较可靠的方法~首先,初始化一个数组,用于后面的事例演示:List<Integer>list=newArrayList<>();......
  • JS动态在父元素里追加元素——insertAdjacentHTML
    insertAdjacentHTML() 方法将指定的文本解析为 Element 元素,并将结果节点插入到DOM树中的指定位置。它不会重新解析它正在使用的元素,因此它不会破坏元素内的现有元素。这避免了额外的序列化步骤,使其比直接使用innerHTML操作更快。 element.insertAdjacentHTML(position,......
  • 面试必刷TOP101:16、删除有序链表中重复的元素-II
    一、题目二、题解importjava.util.*;publicclassSolution{publicListNodedeleteDuplicates(ListNodehead){//空链表if(head==null)returnnull;ListNoderes=newListNode(0);//在链表前加一个表头......