题目
现有一个包含所有正整数的集合 [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 ，并将其从集合中移除。
解题
方法一：有序集合作为补集
创建一个集合set，用于作为无限集合的补集，存储被移除的数。
- 如果补集不是从1开始，那么就插入1
- 如果补集从1开始，就找到第一个非连续的值
class SmallestInfiniteSet { public: set<int> set;//存储去掉的 SmallestInfiniteSet() { } int popSmallest() { auto it=set.begin(); if(set.empty()||*it>1){ set.insert(1); return 1; }else{ int index=1; while(it!=set.end()){ if(*it==index){ it++; index++; }else{ set.insert(index); return index; } } if(it==set.end()){ set.insert(index); return index; } } return -1; } void addBack(int num) { if(set.count(num)){ set.erase(num); } } };
