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最大值为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