2336.无限集中的最小数字

1、题干

现有一个包含所有正整数的集合 [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 <= num <= 1000
• 最多调用 popSmallest 和 addBack 方法 共计 1000 次

2、思路

两个思路：

• 优先队列：直接用优先队列存取数据即可，但要注意数字不能重复，总体最差时间复杂度 $O(n\log{n})$
• 暴力：由于数据范围比较小，可以使用计数排序的思路存取数据进行暴力求解，总体最差时间复杂度 $O(n^2)$

3、代码

优先队列

const N = 1001;
class SmallestInfiniteSet {
    nums = new Array(N).fill(1);
    minQueue = new MinPriorityQueue();
    constructor() {
        for (let i = 1; i < N; i++) {
            this.minQueue.enqueue(i);
        }
    }

    popSmallest(): number {
        const n = this.minQueue.dequeue().element;
        this.nums[n] = 0;
        return n;
    }

    addBack(num: number): void {
        if (this.nums[num]) return;
        this.nums[num] = 1;
        this.minQueue.enqueue(num);
    }
}

暴力

class SmallestInfiniteSet {
    nums: number[] = [];
    constructor() {
        this.nums = new Array(1001).fill(1);
    }

    popSmallest(): number {
        const k = this.nums.findIndex((n, i) => i > 0 && n > 0);
        this.nums[k] = 0;
        return k;
    }

    addBack(num: number): void {
        this.nums[num] = 1;
    }
}