LeetCode: 2336-Smallest Number in Infinite Set 解題紀錄

Last Updated on 2023-04-25 by Clay

題目

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

• SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.
• int popSmallest() Removes and returns the smallest integer contained in the infinite set.
• void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

Example 1:

Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output

[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet(); smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made. smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set. smallestInfiniteSet.addBack(1); // 1 is added back to the set. smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and // is the smallest number, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set. smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.

Constraints:

• 1 <= num <= 1000
• At most 1000 calls will be made in total to popSmallest and addBack.

我們需要實現一個有權重的 set（元素不會重複）類別，其中越小數值的元素其權重越大。我們所實現的這個類別有兩種操作，分別是 addBack() 和 popSmallest()。

popSmallest() 沒什麼好說的，就是回傳當前資料結構中最小的元素。addBack(n) 則是在資料結構中添加 n 的元素。

---

解題思路

我的第一感就是直接透過優先權佇列（priority queue）來實作。並且由於我們希望在資料結構中的元素都是唯一的，所以在彈出（pop）時，要記得把優先權佇列中所有的的最大權重（最小的元素）給彈出。

C++ 範例程式碼

class SmallestInfiniteSet {
public:
    priority_queue<int, vector<int>, greater<int>> pq;
    
    SmallestInfiniteSet() {
        for (int i=1; i<=1000; ++i) {
            addBack(i);
        }
    }
    
    int popSmallest() {
        int small = pq.top();
        pq.pop();

        while (!pq.empty() && small == pq.top()) {
            pq.pop();
        }

        return small;
    }
    
    void addBack(int num) {
        pq.push(num);
    }
};

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
 * int param_1 = obj->popSmallest();
 * obj->addBack(num);
 */

Python 範例程式碼

在 python 中優先權佇列可以使用 heapq 來做。

class SmallestInfiniteSet:

    def __init__(self):
        self.pq = list(range(1, 1001))

    def popSmallest(self) -> int:
        smallest = heapq.heappop(self.pq)

        while self.pq and smallest == self.pq[0]:
            heapq.heappop(self.pq)

        return smallest        

    def addBack(self, num: int) -> None:
        heapq.heappush(self.pq, num)        


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

---

References

• 2336. Smallest Number in Infinite Set

---

Read More

• LeetCode 解題紀錄目錄