做学术用的网站,枣庄住房和城乡建设厅网站,网站开发 培训,做泵阀到哪个网站好题目#xff1a;
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类#xff1a;
SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest() 移除 并返回该无限集中的最小整数。void addBack(int nu…题目
现有一个包含所有正整数的集合 [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 并将其从集合中移除。
题目分析
本题本质就是要实现两个操作1、popSmallest() 2、addBacknum。这里我们遇到第一个问题为什么初始化操作不用去实现。
解决这个问题要我们明确一个前提无限集是无法实际在计算机中存储的。
所以对所谓无限集的操作仅仅是逻辑层面的也就是说并不是创建一个真实的数组实际层面对数组对内层进行操作。而是逻辑上模拟内存的操作并进行输出结果。
接下来考虑如何实现pop和add操作
pop操作既然无限数组没有存在那么我们仅仅需要模拟即可。所以就创建一个变量记录目前弹出的无限集中的最大值的下一个。一开始指向11弹出后指向22弹出后指向3如此循环。
add操作由于上面的pop操作将无限集分为两个部分分别是前面表示已经弹出的部分记为A和后面未弹出的部分记为B所以对于add操作我们必然要考虑是add到哪一部分。如果是B部分则不需要添加如果是A部分则需要添加进入数组由于下次pop时必然是pop这里新加入的数所在的A部分中的最小数所以这里要创建一个集合用来存储add到A的数据。考虑到pop是弹出A中的最小值所以要时刻保持集合中的数据有序这里就采用set集合来保证。set集合内部维护采用的是堆排序。
当然分析到这里add会导致pop的方法改变。
图解分析
代码如下
class SmallestInfiniteSet {
public:SmallestInfiniteSet() {}int popSmallest() {if (s.empty()) {int ans thres;//thres就是分析中的tthres;return ans;}int ans *s.begin();s.erase(s.begin());return ans;}void addBack(int num) {if (num thres) {s.insert(num);}}private:int thres 1;setint s;//s就是分析中的a集合
};