无限集中的最小数字

标签: 设计 哈希表 堆（优先队列）

难度: Medium

现有一个包含所有正整数的集合 [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 次

Submission

运行时间: 68 ms

内存: 17.0 MB

class SmallestInfiniteSet:

    def __init__(self):
        self.val = 0
        self.lst = []
        heapq.heapify(self.lst)

    def popSmallest(self) -> int:
        if self.lst:
            return heapq.heappop(self.lst) if self.lst else None
        else:
            self.val += 1
            return self.val


    def addBack(self, num: int) -> None:
        if num <= self.val and num not in self.lst:
            heapq.heappush(self.lst, num)
            



# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)

Explain

这个题解使用了一个整数val来记录当前未被移除的最小整数，以及一个最小堆lst来存储被重新加入的数字。初始化时，val设置为0，lst为空。当调用popSmallest()时，如果lst非空，则从lst中移除并返回最小元素；如果lst为空，则直接返回val并增加val。对于addBack(num)，只有当num小于等于val且不在lst中时，才将num加入lst。这确保了所有被加回的数字都是之前被移除的数字。

时间复杂度: O(log n)

空间复杂度: O(n)

class SmallestInfiniteSet:

    def __init__(self):
        self.val = 0  # 记录当前未删除的最小整数
        self.lst = []  # 存储被重新加入的数字的最小堆
        heapq.heapify(self.lst)  # 将lst转换为最小堆

    def popSmallest(self) -> int:
        if self.lst:
            return heapq.heappop(self.lst)  # 如果lst非空，弹出并返回最小值
        else:
            self.val += 1  # 否则，返回当前最小值并更新val
            return self.val

    def addBack(self, num: int) -> None:
        if num <= self.val and num not in self.lst:
            heapq.heappush(self.lst, num)  # 如果num小于等于val且不在lst中，将其加入lst

Explore

初始化`self.val`为0而不是1会导致第一次调用`popSmallest()`方法时返回0，这与预期从1开始返回最小整数不符。这意味着整个数集的起始点被错误地设置为0。这种偏差将使得所有后续的数字也相应地偏移，每个数字都比预期小1。

这样的条件判断确保只有已经被`popSmallest()`方法移除且未被再次移除的数字才能被重新加入。`num <= self.val`确保添加的数字是在当前最小值`self.val`之前的，即它们是之前已经被访问过的。同时，检查`num`是否已在`lst`中可以避免重复添加相同的数字，这有助于保持`lst`的正确性和最小堆的性能。

是的，这种操作可以保证每次都返回集合中当前最小的整数。当`lst`为空时，`self.val`记录了下一个未被移除的最小整数。返回`self.val`并随后增加其值可以确保连续调用`popSmallest()`时能够依次返回递增的最小整数。只有当`lst`不为空时，这个逻辑才会检查堆中是否有更小的、先前被移除但又被加回的数字。

使用最小堆维护`lst`可以高效地支持这两个操作。对于`popSmallest`方法，最小堆能够在常数时间O(1)内提供最小值，并且可以在对数时间O(log n)内移除最小值。对于`addBack`方法，最小堆可以在对数时间O(log n)内插入新元素。这样的时间复杂度是非常适合频繁进行这两种操作的场景，确保了整体操作的效率。