2336.无限集中的最小数字

链接：2336.无限集中的最小数字
难度：Medium
标签：设计、哈希表、堆（优先队列）
简介：现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。实现 SmallestInfiniteSet 类。

题解 1 - python

• 编辑时间：2023-11-29
• 执行用时：92ms
• 内存消耗：16.58MB
• 编程语言：python
• 解法介绍：堆。

class SmallestInfiniteSet:
    def __init__(self):
        self.nmin = 1
        self.q = []
        self.used = set()
    def popSmallest(self) -> int:
        if not self.q:
            self.nmin += 1
            return self.nmin - 1
        num = heappop(self.q)
        self.used.remove(num)
        return num
    def addBack(self, num: int) -> None:
        if self.nmin > num and num not in self.used:
            heappush(self.q, num)
            self.used.add(num)