解題程式碼

var SmallestInfiniteSet = function () {
  this.minHeap = new MinPriorityQueue();
  this.set = new Set();
  this.min = 1;
};

SmallestInfiniteSet.prototype.popSmallest = function () {
  if (this.set.size === 0) {
    let val = this.min;
    this.min++;
    return val;
  } else {
    let val = this.minHeap.dequeue().element;
    this.set.delete(val);
    return val;
  }
};

SmallestInfiniteSet.prototype.addBack = function (num) {
  if (!this.set.has(num) && num < this.min) {
    this.minHeap.enqueue(num);
    this.set.add(num);
  }
};

解題思路、演算法

這題測資很小，At most 1000 calls will be made in total to popSmallest and addBack.，這用暴力解也行。

但要做到讓效能最好，要建一個 Min Heap，實作 add & remove 函式，然後使用三個變數 hashSet、minHeap、minVal 去處理 popSmallest 函式和 addBack 函式的邏輯。

popSmallest 函式: 只要 minHeap or hashSet 裡面沒東西，就取 minVal，然後 minVal 增加 1。若有 addBack 回來的任何值，就會出現在 minHeap，以 minHeap 內的值為優先回傳。

addBack 函式: 主要就是要判斷是否可以加回 hashSet，有兩個條件，hashSet 沒出現且小於 minVal，小於 minVal 能確定已經是取出過的值。

解法的時間、空間複雜度

時間複雜度: 兩個函式皆 O(log n)
空間複雜度: O(n)

參考資料

[](https://www.youtube.com/watch?v=2336. Smallest Number in Infinite Set)