LeetCode 2336. 无限集中的最小数字（SortedSet）

Michael阿明

发布于 2022-07-31 09:35:19

2750

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

文章目录
1. 题目
2. 解题

1. 题目

现有一个包含所有正整数的集合 [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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

使用有序set，插入数据后会自动排序

from sortedcontainers import SortedSet
class SmallestInfiniteSet:

    def __init__(self):
        self.s = SortedSet(range(1, 1001))

    def popSmallest(self) -> int:
        return self.s.pop(0)

    def addBack(self, num: int) -> None:
        self.s.add(num)

232 ms 16.3 MB Python3

我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-30，如有侵权请联系 cloudcommunity@tencent.com 删除

https