Home Coding Leetcode Medium

⭐️⭐️

# 題目敘述

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.

# Solution

class SmallestInfiniteSet {
private:
    int min_num = 1;
    priority_queue<int, vector<int>, greater<int>> pq;
    unordered_set<int> nums;
public:
    SmallestInfiniteSet() {
        pq = priority_queue<int, vector<int>, greater<int>>();
        nums = unordered_set<int>();
    }
    
    int popSmallest() {
        if (!pq.empty()) {
            int res = pq.top();
            pq.pop();
            nums.erase(res);
            return res;
        }
        min_num++;
        return min_num - 1;
    }
    
    void addBack(int num) {
        if (min_num > num && nums.find(num) == nums.end()) {
            pq.push(num);
            nums.insert(num);
        }
    }
};
import java.util.PriorityQueue;
class SmallestInfiniteSet {
    PriorityQueue<Integer> pQ;
    public SmallestInfiniteSet() {
        pQ = new PriorityQueue<>();
        for(int i = 1; i <= 1000; i++){
            pQ.add(i);
        }
    }
    
    public int popSmallest() {
        int num = pQ.poll();
        return num;
    }
    
    public void addBack(int num) {
        if(!pQ.contains(num)){
            pQ.add(num);
        }
    }
}
class SmallestInfiniteSet:
    def __init__(self):
        self.min_num = 1
        self.pq = []        
    def popSmallest(self) -> int:
        if self.pq:
            return heapq.heappop(self.pq)
        self.min_num += 1
        return self.min_num - 1
    def addBack(self, num: int) -> None:
        if self.min_num > num and num not in self.pq:
            heapq.heappush(self.pq, num)