无限集中的最小数字-LeetCode

无限集中的最小数字

🎯 问题描述（来源于LeetCode）

描述：
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...]。请你设计并实现 SmallestInfiniteSet 类。

说明：

• SmallestInfiniteSet()：初始化对象，包含所有正整数。

• int popSmallest()：移除并返回集合中的最小整数。

• void addBack(int num)：如果 num 不在集合中，将其添加回集合。

• 示例：

  • 示例 1：

    输入：["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest"]
         [[], [2], [], []]
    输出：[null, null, 1, 2]
    解释：初始集合为 [1,2,3,...]。addBack(2) 无效因为2还在。第一次弹出1，第二次弹出2。

  • 示例 2：

    输入：["SmallestInfiniteSet", "popSmallest", "popSmallest", "addBack", "popSmallest"]
         [[], [], [], [1], []]
    输出：[null, 1, 2, null, 1]
    解释：弹出1和2后，集合包含3开始的数。将1加回后，再次弹出的是1。

💻 解题思路

思路1：预填充最小堆 + 哈希集合

代码实现

import heapq

class SmallestInfiniteSet:
    def __init__(self):
        # 初始化包含1到1000所有正整数的最小堆
        self.heap = list(range(1, 1001))
        heapq.heapify(self.heap)
        # 用集合记录已被移除的数字
        self.removed = set()

    def popSmallest(self) -> int:
        # 移除并返回集合中的最小整数
        num = heapq.heappop(self.heap)
        self.removed.add(num)
        return num

    def addBack(self, num: int) -> None:
        # 将指定数字添加回集合中（如果该数字确实被移除过）
        if num in self.removed:
            heapq.heappush(self.heap, num)
            self.removed.remove(num)

📊 性能分析

• 时间复杂度：$O(\log n)$。其中 popSmallest 和 addBack 涉及堆的插入删除操作；初始化为 $O(n)$。
• 空间复杂度：$O(n)$。主要为堆和集合占用的空间。

💡 思考

利用题目限制（最多调用1000次），通过预填充1-1000避免了处理无限大的逻辑。使用 heapq 维护最小值，配合 set 防止重复添加，是处理此类模拟题的常用技巧。