2336. Smallest Number in Infinite Set

Leetcode link

题目简介

var SmallestInfiniteSet = function() {};

/**
 * @return {number}
 */
SmallestInfiniteSet.prototype.popSmallest = function() {};

/** 
 * @param {number} num
 * @return {void}
 */
SmallestInfiniteSet.prototype.addBack = function(num) {};

题目要求我们实现一个 SmallestInfiniteSet，内部保存着所有的正整数，并且有两个主要方法：

• popSmallest：把当前最小的正整数从 SmallestInfiniteSet 删除并返回
• addBack：把数字重新加回 SmallestInfiniteSet，不允许 SmallestInfiniteSet 中有重复的数字

解题思路

这题我们可以用一个变量 minNum 来表示当前记录的最小数字，每次 pop 的时候只需要把当前 minNum 返回后加一即可

为了兼容 addBack，我们可以用一个小顶堆 heap 来记录小于 minNum 且被加回来的数字

如此一来，popSmallest 时我们需要做两件事：

1. 判断 heap 中是否有数字，如果有，则从 heap 中取数
2. 如果没有，则直接从 minNum 取

而在 addBack 中，我们需要判断：

1. 当前数字是否小于 nimNum，如果是，则判断是否 heap 中已经有这个数字，如果没有则 push 进 heap
2. 如果数字大于 minNum 或者 heap 中已经有该数字，则什么都不做直接返回

Javascript

var SmallestInfiniteSet = function () {
    this.minNum = 1
    this.heap = new PriorityQueue((a, b) => a - b)
};

/**
 * @return {number}
 */
SmallestInfiniteSet.prototype.popSmallest = function () {
    if(this.heap.size() > 0) {
        return this.heap.pop()
    }
    return this.minNum++
};

/** 
 * @param {number} num
 * @return {void}
 */
SmallestInfiniteSet.prototype.addBack = function (num) {
    if(num < this.minNum && !this.heap.contains(val => val === num)) {
        this.heap.push(num)
    }
};

/** 
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * var obj = new SmallestInfiniteSet()
 * var param_1 = obj.popSmallest()
 * obj.addBack(num)
 */

复杂度分析

n 代表 heap 中的元素个数

时间

SmallestInfiniteSet：O(1)

popSmallest: O(logn) 因为 pop 方法是 O(logn)

addBack：O(n) 因为 contains 方法是 O(n) 、push 方法是 O(long)

空间

来源于 heap，O(n)