LeetCode 2336. 无限集中的最小数字：有序集合

本文主要是介绍LeetCode 2336. 无限集中的最小数字：有序集合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【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)