Leetcode2336 无限集中的最小数字

题目：

现有一个包含所有正整数的集合 [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、popSmallest() 2、addBack（num）。这里我们遇到第一个问题为什么初始化操作不用去实现。

解决这个问题要我们明确一个前提：无限集是无法实际在计算机中存储的。

所以对所谓无限集的操作仅仅是逻辑层面的，也就是说并不是创建一个真实的数组实际层面对数组对内层进行操作。而是逻辑上模拟内存的操作并进行输出结果。

接下来考虑如何实现pop和add操作：

pop操作：既然无限数组没有存在，那么我们仅仅需要模拟即可。所以就创建一个变量，记录目前弹出的无限集中的最大值的下一个。一开始指向1，1弹出后指向2，2弹出后指向3，如此循环。

add操作：由于上面的pop操作将无限集分为两个部分（分别是前面表示已经弹出的部分记为A，和后面未弹出的部分记为B），所以对于add操作，我们必然要考虑是add到哪一部分。如果是B部分，则不需要添加；如果是A部分，则需要添加进入数组，由于下次pop时必然是pop这里新加入的数所在的A部分中的最小数，所以这里要创建一个集合，用来存储add到A的数据。考虑到pop是弹出A中的最小值，所以要时刻保持集合中的数据有序，这里就采用set集合来保证。set集合内部维护采用的是堆排序。

当然分析到这里add会导致pop的方法改变。

图解分析：

代码如下：

class SmallestInfiniteSet {
public:
    SmallestInfiniteSet() {}
    
    int popSmallest() {
        if (s.empty()) {
            int ans = thres;//thres就是分析中的t
            ++thres;
            return ans;
        }
        int ans = *s.begin();
        s.erase(s.begin());
        return ans;
    }
    
    void addBack(int num) {
        if (num < thres) {
            s.insert(num);
        }
    }
private:
    int thres = 1;
    set<int> s;//s就是分析中的a集合
};