【每日一题】无限集中的最小数字

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：有限集合
- 方法二：有序集合
写在最后

Tag

【有序集合】【2023-11-29】

题目来源

2336. 无限集中的最小数字

题目解读

设计一个类实现移除无限集中的最小整数以及向该无限集中增加一个原集合中不存在的整数。

解题思路

方法一：有限集合

因为题目中提示的 1 <= num <= 1000，并且两个方法的调用次数共计最多 1000 次，于是可以维护一个容纳整数 1-1000 的有序集合，popSmallest 直接返回 *s.begin()，addBack 直接将 num 插入集合。

实现代码

class SmallestInfiniteSet {
public:
    set<int> s;
    SmallestInfiniteSet() {
        s.clear();
        for(int i = 1; i <= 1010; ++i) {
            s.insert(i);
        }
    }
    
    int popSmallest() {
        int x = *s.begin();
        s.erase(s.begin());
        return x;
    }
    
    void addBack(int num) {
        s.insert(num);
    }
};

复杂度分析

时间复杂度：初始化的时间复杂度为 $O (n)$ ， $n = 1000$ ；popSmallest 和 addBack 的时间复杂度为 $O (l o g n)$ ；

空间复杂度： $O (n)$ 。

方法二：有序集合

方法一中使用的其实是有限集合，因为题目提示的数据范围比较小，我们直接将所有数据存入到到有序集合中，一旦数据规模大，该方法就会失效。现在使用一种真正的有限集合来解决本题。

由于一开始的集合中包含所有从 1 开始的正整数，并且操作要么是增加任意的正整数，要么是删除最小的正整数，因此在任意时刻，会有一个 threshold，使得所有大于等于 threshold 的正整数均在集合中。并且这个 threshold 不会很大，不会超过 k+1，因为最多调用 k 次 popSmallest，并且每次的调用操作都是移除集合中最小的整数。

于是可以维护一个有序集合 s 保存所有小于 threshold 的正整数，用 threshold 表示所有大于等于 threshold 的正整数：

在 popSmallest 中，如果 s 为空时，表明当前没有小于 threshold 的整数，直接返回 threshold 并 ++threshold；否则直接移除并返回集合 s 中的最小元素；
在 addBack 中，如果 num 大于等于 threshold，则不进行任何操作，否则将其加入到 s 中。

实现代码

class SmallestInfiniteSet {
private:
    set<int> s;
    int threshold = 1;
public:
    SmallestInfiniteSet() {
    }
    
    int popSmallest() {
        if (s.empty()) {
            int res = threshold;
            ++threshold;
            return res;
        }
        int res = *s.begin();
        s.erase(s.begin());
        return res;
    }
    
    void addBack(int num) {
        if (num < threshold) {
            s.insert(num);
        }
    }
};