【LetMeFly】2336.无限集中的最小数字：有序集合

力扣题目链接：https://leetcode.cn/problems/smallest-number-in-infinite-set/

现有一个包含所有正整数的集合 [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 次

方法一：有序集合

使用一个整数continuousSmallest记录“连续的正整数的最小值”（初始值为1）；使用一个有序集合记录新插入的比continuousSmallest还小的整数。

• 移除整数时，若有序集合非空，则返回有序集合中第一个元素（最小的元素）；否则，返回continuousSmallest并令其加一
• 加入整数时，若待加整数大于等于continuousSmallest，则忽略；否则，往有序集合中插入这个元素

以上。

• 时间复杂度$O(1)$或$O(\log n)。若没涉及到集合，则时间复杂度为$O(1)$，否则为$O(\log n)$
• 空间复杂度$O(n)。实际大小为集合中同时存在的最多元素个数。（插入的数小于最小连续整数）

AC代码

C++

class SmallestInfiniteSet {
private:int continuousSmallest;set<int> added;
public:SmallestInfiniteSet() {continuousSmallest = 1;}int popSmallest() {if (added.size()) {int ans = *added.begin();added.erase(added.begin());return ans;}return continuousSmallest++;}void addBack(int num) {if (num >= continuousSmallest) {return;}added.insert(num);}
};

Python

from sortedcontainers import SortedSet 
# sortedcontainers不是Python自带的，需要pip install
# 力扣中默认不具有此函数，因此不能被注释掉class SmallestInfiniteSet:def __init__(self):self.continuousSmallest = 1self.added = SortedSet()def popSmallest(self) -> int:if self.added:return -self.added.pop()self.continuousSmallest += 1return self.continuousSmallest - 1def addBack(self, num: int) -> None:if num >= self.continuousSmallest:returnself.added.add(-num)

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134687046