无限集中的最小数字

周赛题

Leetcode Link: 无限集中的最小数字 - 力扣 (LeetCode) 竞赛

题目

现有一个包含所有正整数的集合 [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 ，并将其从集合中移除。

解法一

思路： 题目中是无限集，无限集不能表示，因此我们只保存不在这个集合中的数字即可。

题解：

class SmallestInfiniteSet:
 
    def __init__(self):
        self.not_exist = set()
 
    def popSmallest(self) -> int:
        i=1
        while(1):
            if i not in self.not_exist:
                self.not_exist.add(i)
                return i
            else:
                i+=1
 
    def addBack(self, num: int) -> None:
        if num in self.not_exist:
            self.not_exist.remove(num)
        return
 

解法二

思路：

题解：

解法三

思路：

题解：

启发和联系