题目
现有一个包含所有正整数的集合
[1, 2, 3, 4, 5, ...]。实现
SmallestInfiniteSet类：
SmallestInfiniteSet()初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest()移除 并返回该无限集中的最小整数。void addBack(int num)如果正整数num不 存在于无限集中，则将一个num添加 到该无限集中。
解题思路
- 正整数是无限的所以，需要存储的时被移除的数据；
- 通过使用Map来存储移除的数据；
- 移除无限集中的最小整数即Map中不存在的最小整数；
- 添加数据到无限集中，即从Map中删除该数据。
代码展示
class SmallestInfiniteSet { Map<Integer,Integer> data = null; public SmallestInfiniteSet() { data = new TreeMap<>(); } public int popSmallest() { int index = 1; while (index <= data.size()){ if(!data.containsKey(index)){ break; } index++; } data.put(index, index); return index; } public void addBack(int num) { data.remove(num); } }
