首页 > 编程语言 >(算法)数据流中的第K⼤元素————<堆>

(算法)数据流中的第K⼤元素————<堆>

时间:2024-09-02 15:55:03浏览次数:14  
标签:KthLargest val nums int 元素 算法 heap 数据流 size

1. 题⽬链接:703.数据流中的第K⼤元素

2. 题⽬描述:

3. 解法(优先级队列):

算法思路:

我相信,看到TopK 问题的时候,兄弟们应该能⽴⻢想到「堆」,这应该是刻在⻣⼦⾥的记忆。

 C++算法代码:

class KthLargest 
{
public:
    //创建一个小根堆
    priority_queue<int,vector<int>,greater<int>>heap;
    int _k;
    KthLargest(int k, vector<int>& nums) 
    {
        _k=k;
        for(int key:nums)
        {
            heap.push(key);
            if(heap.size()>k)
            {
                heap.pop();
            }
        }
    }
    
    int add(int val) 
    {
        heap.push(val);
        if(heap.size()>_k)
        {
            heap.pop();
        }
        return heap.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

Java算法代码:

class KthLargest
{
	// 创建⼀个⼤⼩为 k 的⼩根堆 
	PriorityQueue<Integer> heap;
	int _k;
	public KthLargest(int k, int[] nums)
	{
		_k = k;
		heap = new PriorityQueue<>();
		for (int x : nums)
		{
			heap.offer(x);
			if (heap.size() > _k)
			{
				heap.poll();
			}
		}
	}

	public int add(int val)
	{
		heap.offer(val);
		if (heap.size() > _k)
		{
			heap.poll();
		}
		return heap.peek();
	}
}
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

标签:KthLargest,val,nums,int,元素,算法,heap,数据流,size
From: https://blog.csdn.net/2301_79580018/article/details/141821879

相关文章

  • (算法)最后⼀块⽯头的重量————<堆>
    1.题⽬链接:1046.最后⼀块⽯头的重量2.题⽬描述:3.解法(利⽤堆):算法思路:其实就是⼀个模拟的过程:•每次从⽯堆中拿出最⼤的元素以及次⼤的元素,然后将它们粉碎;•如果还有剩余,就将剩余的⽯头继续放在原始的⽯堆⾥⾯重复上⾯的操作,直到⽯堆⾥⾯只剩下⼀个元素,或者没有元......
  • 【代码随想录Day6】哈希表Part01|判断一个元素是否出现集合里
    哈希表理论基础文章讲解:哈希表理论基础要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。242.有效的字母异位词题目链接/文章讲解/视频讲解:有效的字母异位词定义一个哈希表record,遍历s,记录s中每个字母出现的次数,遍历t,减去t中每个字母出现的次数,遍历......
  • 2.多数元素
    给定一个大小为n__的数组nums,返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。示例1:输入:nums=[3,2,3]输出:3示例2:输入:nums=[2,2,1,1,1,2,2]输出:2解法1:HashMapclassSolution......
  • 一个数独生成算法
    思路:创建一个9*9的数独数组,挨个往里面插入1-9的数值,并且验证该数值插入是否合理,该数值插入之后是否会导致生成错误数据,最后生成一张随机数独数据functiongetShuDu(){//创建初始数组letshudu=newArray(9);for(leti=0;i<9;i++){shudu[i]=newArray(9).fill(0)......
  • 代码随想录day48 || 739, 每日温度 496, 下一个更大元素 I 503, 下一个更大元素II
    739每日温度funcdailyTemperatures(temperatures[]int)[]int{ //双指针 varres=make([]int,len(temperatures)) fori:=0;i<len(temperatures);i++{ forj:=i+1;j<len(temperatures);j++{ iftemperatures[j]>temperatures[i]{ res[i]=j......
  • 书籍-《空间导航与跟踪:分析与算法》
    编辑:陈萍萍的公主@一点人工一点智能书籍:NavigationandTrackinginSpace:AnalysisandAlgorithms作者:SanatK.Biswas,AndrewG.Dempster出版:ArtechHouse01书籍介绍本书专注于人造空间物体的导航与跟踪,重点是对一系列广泛的空间任务进行动力学建模,包括:地球轨道卫星任务、发射......
  • 分布式概念及选举算法
    概念  由很多自主的计算机组成。很容易地把运行在不同计算机上的不同应用程序集成到单个系统中。清晰的记录接口。轻松的扩展。分布式类型:分布式计算系统、分布式信息系统(数据处理)互斥    集中式算法      每个程序在需要访问临界资源时,先给协调......
  • 基于FP-Growth算法进行数据集中频繁项集挖掘
    FP-Growth算法的主要步骤构建FP树(FrequentPatternTree):首先,扫描数据集一次,找出频繁项,并按支持度降序排列。然后,构建FP树,这是一个压缩表示的数据结构,其中每个项集对应树中的一个路径。挖掘FP树:从FP树中递归地挖掘频繁项集。这个过程通常从支持度最低的频繁项开始,逐步向上挖掘......
  • 基于C语言的选择排序算法
    一、选择排序算法的基本原理        选择排序算法是一种简单直观的排序算法。其基本原理为:        首先,将待排序的数组划分为已排序和未排序两部分。初始时,已排序部分为空,未排序部分为整个数组。        在每一轮排序中,从未排序部分找出最小(或最大)......
  • 基于C语言的归并排序算法
    一、归并排序的基本概念        归并排序(MergeSort)是一种基于分治法思想的高效稳定排序算法。其基本原理是将一个待排序的数组不断地分割成较小的子数组,直到每个子数组只包含一个元素,此时每个子数组都被认为是有序的。然后,再将这些有序的子数组合并成一个更大的有序......