本文主要是介绍LeetCode、2336. 无限集中的最小数字（中等，小顶堆），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
博主所有博客文件目录索引：博客目录索引(持续更新)
LeetCode、2336. 无限集中的最小数字
题目链接及类型
题目链接：2336. 无限集中的最小数字
类型：数据结构/优先队列
思路
首先读题：包含有一个正整数的无限集合，如：集合 [1, 2, 3, 4, 5, ...] 。包含两个操作：①popSmallest：移除并得到一个集合中的最小元素。②addBack(int num)：若是当前集合中不存在该元素num，则将该元素添加到集合中！【注意这里集合中是具有唯一性】
在这里我们选择小顶堆数据结构，第一个永远是集合中最小的元素，并且插入操作时间复杂度为O(logn)，取得最小值复杂度为O(1)。
对于其中的无限正整数，我们可以使用一个变量thres来定义，初始值为1，是否需要提前将大量的数字填充到集合中呢？并不需要，若是在popSmallest时我们的小顶堆为空时，我们可以根据thres值来进行返回。若是进行addBack时，一旦填入的num值<thres才添加到集合中。
上面的思路有了，那么还要注意的一点就是在进行addBack时要防止num<thres情况多次进行调用，若是我们不判断唯一性，那么可能会将重复值多次添加到队列当中。所以这里我们会使用一个boolean的vis数组来表示是否访问过。
代码题解
复杂度分析：时间复杂度O(n.logn)；空间复杂度O(n)
//注意：要考虑到元素的唯一性!!!也就是说在集合中无法同时存在两个元素值相同的元素
class SmallestInfiniteSet {public boolean[] vis;public PriorityQueue<Integer> queue;public int thres;public SmallestInfiniteSet() {this.vis = new boolean[1001];//题目说了num最大值为1000this.queue = new PriorityQueue<>((o1, o2)->o1.compareTo(o2));//小顶堆this.thres = 1;}public int popSmallest() {if (queue.isEmpty()) {int ans = thres;thres ++;return ans;}int ans = queue.poll();vis[ans] = false;return ans;} //在进行添加时，当num<thres时，连续进行两次add调用，那么此时若是没有唯一性判断就会添加两个相同的元素到集合中//为了避免这种情况，就需要使用一个vis数组来表示唯一性public void addBack(int num) {if (num < thres && !vis[num]) {queue.offer(num);vis[num] = true;}}
}
整理者：长路 时间：2024.1.15
这篇关于LeetCode、2336. 无限集中的最小数字（中等，小顶堆）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
