力扣---2336. 无限集中的最小数字-526互联

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类：

SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含所有正整数。
int popSmallest() 移除并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不存在于无限集中，则将一个 num 添加到该无限集中。

示例：

输入
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]

解释
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 已经在集合中，所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。
smallestInfiniteSet.addBack(1); // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，
// 且 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。

提示：

1 <= num <= 1000
最多调用 popSmallest 和 addBack 方法共计 1000 次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/smallest-number-in-infinite-set
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

由于集合长度时无限的，所以直接用一个列表啥的模拟是不现实的（虽然由于数据大小的限制，还是可以强行模拟，但这就变成面向测试用例编程了）。

由于每次都是获取最小的那个数。当没有新数据加入时，可以利用一个不断自增的变量 count 来模拟无限长度的集合。

当加入新数据时，可以考虑两点：
1. 新数据大于等于 count 时，不需要添加进无限长度的集合中（集合中不包含相同元素）
2. 新数据小于 count 时，可以使用一个优先队列来维护新数据，当优先队列为 null 时，则使得 count 自增。

class SmallestInfiniteSet {
    // 优先队列，维护所有小于当前 count 的新增数据。
    PriorityQueue<Integer> priorityQueue;
    // 哈希表，保证优先队列中的元素没有重复。
    Set<Integer> set;
    // 自增元素，动态模拟无限长的集合。
    int count = 1;

    public SmallestInfiniteSet () {
        this.priorityQueue = new PriorityQueue<>();
        this.set = new HashSet<>();
    }

    public int popSmallest () {
        // 优先队列为 null 时，直接从无限长的集合中获取最小值，即 count 的当前值即可。
        if (priorityQueue.isEmpty()) {
            return count++;
        }
        // 优先队列不为 null 时，意味着之前添加了小于当前无限长集合中最小值的元素，此时需要从这些元素中进行删除。
        else {
            int tem = priorityQueue.poll();
            // 保证优先队列中不包含相同元素。
            set.remove(tem);
            return tem;
        }
    }

    public void addBack (int num) {
        // 保证优先队列中的元素都是需要优先删除，且保证优先队列中不包含相同元素。
        if (num < count && !set.contains(num)) {
            priorityQueue.add(num);
            set.add(num);
        }
    }
}