2336. 无限集中的最小数字
现有一个包含所有正整数的集合 [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 <= 1000popSmallest 和 addBack 方法 共计 1000 次原站题解
javascript 解法, 执行用时: 128 ms, 内存消耗: 48.2 MB, 提交时间: 2023-11-29 07:24:16
var SmallestInfiniteSet = function() {
this.thres = 1;
this.s = new Set();
this.pq = new MinPriorityQueue();
};
/**
* @return {number}
*/
SmallestInfiniteSet.prototype.popSmallest = function() {
let ans = 0;
if (this.s.size == 0) {
ans = this.thres;
this.thres++;
return ans;
}
ans = this.pq.dequeue().element;
this.s.delete(ans);
return ans;
};
/**
* @param {number} num
* @return {void}
*/
SmallestInfiniteSet.prototype.addBack = function(num) {
if (num < this.thres && !this.s.has(num)) {
this.s.add(num);
this.pq.enqueue(num);
}
};
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* var obj = new SmallestInfiniteSet()
* var param_1 = obj.popSmallest()
* obj.addBack(num)
*/
golang 解法, 执行用时: 32 ms, 内存消耗: 7.1 MB, 提交时间: 2023-11-29 07:23:30
type SmallestInfiniteSet struct {
thres int
s *treeset.Set
}
func Constructor() SmallestInfiniteSet {
return SmallestInfiniteSet{
thres:1,
s:treeset.NewWithIntComparator(),
}
}
func (this *SmallestInfiniteSet) PopSmallest() int {
if this.s.Empty() {
ans := this.thres
this.thres++
return ans
}
it := this.s.Iterator()
it.Next()
ans := it.Value().(int)
this.s.Remove(ans)
return ans
}
func (this *SmallestInfiniteSet) AddBack(num int) {
if num < this.thres {
this.s.Add(num)
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.PopSmallest();
* obj.AddBack(num);
*/
python3 解法, 执行用时: 116 ms, 内存消耗: 17 MB, 提交时间: 2023-11-29 07:23:03
from sortedcontainers import SortedSet
class SmallestInfiniteSet:
def __init__(self):
self.thres = 1
self.s = SortedSet()
def popSmallest(self) -> int:
s_ = self.s
if not s_:
ans = self.thres
self.thres += 1
return ans
ans = s_[0]
s_.pop(0)
return ans
def addBack(self, num: int) -> None:
s_ = self.s
if num < self.thres:
s_.add(num)
# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)
java 解法, 执行用时: 9 ms, 内存消耗: 43.3 MB, 提交时间: 2023-11-29 07:22:48
class SmallestInfiniteSet {
private int thres;
private TreeSet<Integer> set;
public SmallestInfiniteSet() {
thres = 1;
set = new TreeSet<Integer>();
}
public int popSmallest() {
if (set.isEmpty()) {
int ans = thres;
++thres;
return ans;
}
int ans = set.pollFirst();
return ans;
}
public void addBack(int num) {
if (num < thres) {
set.add(num);
}
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
* obj.addBack(num);
*/
cpp 解法, 执行用时: 60 ms, 内存消耗: 35.1 MB, 提交时间: 2023-11-29 07:22:25
class SmallestInfiniteSet {
public:
SmallestInfiniteSet() {}
int popSmallest() {
if (s.empty()) {
int ans = thres;
++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;
};
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet* obj = new SmallestInfiniteSet();
* int param_1 = obj->popSmallest();
* obj->addBack(num);
*/
cpp 解法, 执行用时: 104 ms, 内存消耗: 45.4 MB, 提交时间: 2023-11-29 07:21:38
class SmallestInfiniteSet {
public:
set<int>s;
SmallestInfiniteSet() {
s.clear();
for(int i=1;i<=1010;i++)s.insert(i);
}
int popSmallest() {
int x=*s.begin();
s.erase(s.begin());
return x;
}
void addBack(int num) {
s.insert(num);
}
};
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet* obj = new SmallestInfiniteSet();
* int param_1 = obj->popSmallest();
* obj->addBack(num);
*/
python3 解法, 执行用时: 116 ms, 内存消耗: 15.6 MB, 提交时间: 2022-11-21 16:11:43
class SmallestInfiniteSet:
def __init__(self):
self.p = list(range(1,1001))
heapq.heapify(self.p)
self.cur = set()
def popSmallest(self) -> int:
t = heapq.heappop(self.p)
self.cur.add(t)
return t
def addBack(self, num: int) -> None:
if num in self.cur:
heapq.heappush(self.p, num)
self.cur.remove(num)
# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)
golang 解法, 执行用时: 132 ms, 内存消耗: 7.1 MB, 提交时间: 2022-11-21 16:10:30
type SmallestInfiniteSet map[int]bool
func Constructor() SmallestInfiniteSet { return SmallestInfiniteSet{} }
func (s SmallestInfiniteSet) PopSmallest() int {
for i := 1; ; i++ {
if !s[i] {
s[i] = true
return i
}
}
}
func (s SmallestInfiniteSet) AddBack(n int) {
delete(s, n)
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.PopSmallest();
* obj.AddBack(num);
*/