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++
1 |
|
Python
1 |
|
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/134687046
2336.无限集中的最小数字
https://blog.letmefly.xyz/2023/11/29/LeetCode 2336.无限集中的最小数字/