题目
现有一个包含所有正整数的集合
[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); } }