题目

现有一个包含所有正整数集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类:

示例

输入
["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操作:既然无限数组没有存在,那么我们仅仅需要模拟即可。所以就创建一个变量记录目前弹出的无限集中的最大值的下一个。一开始指向1,1弹出后指向2,2弹出后指向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就是分析中的t
            ++thres;
            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;
    set<int&gt; s;//s就是分析中的a集合
};

原文地址:https://blog.csdn.net/m0_67656158/article/details/134694557

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_17455.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注