前言
博主所有博客文件目录索引：博客目录索引(持续更新)
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最大值为1000
this.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
