【Leetcode Daily】2336无限集中的最小数字

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是要实现一个数据结构，这个结构初始是一个正整数集合，要求能返回集合中的最小值，并随时往集合里加正整数。

思路分享

• 返回最小值，可以用堆来维护，至于堆是维护新加的，还是已有的，就看具体实现方式。但都需要思考如何去重，避免重复添加。

• 官方题解提到了 SortedSet，可以在完成堆的任务的同时，高效去重。就不需要像参考题解这样，又用堆，也用 Set 了。

  https://leetcode.cn/problems/smallest-number-in-infinite-set/solutions/2542156/wu-xian-ji-zhong-de-zui-xiao-shu-zi-by-l-5mfr/

代码解答（强烈建议自行解答后再看）

• 参考题解

class SmallestInfiniteSet:
    def __init__(self):
        self.heap = [1]
        self.rec = set()
        heapify(self.heap)

    def popSmallest(self) -> int:
        # print("pop")
        res = heappop(self.heap)
        self.rec.add(res)
        if len(self.heap) == 0:
            heappush(self.heap, res+1)
        # print(list(self.heap))
        # print(self.rec)
        return res

    def addBack(self, num: int) -> None:
        print(f"add {num}")
        if not num in self.rec:
            return
        heappush(self.heap, num)
        self.rec.discard(num)
        # print(list(self.heap))
        # print(self.rec)


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