Leetcode 6113. The smallest number in an infinite set

1. Problem description

2. Solution

Solution 1 ：

Hash Responsible for the marker in the set true, Absent is false, And in popSmallest and addBack In the process of , Maintain a minimum value dynamically

class SmallestInfiniteSet {
    

    private Boolean[] Hash;
    private int Min;

    public SmallestInfiniteSet() {
    
        Hash = new Boolean[2001];
        Arrays.fill(Hash, true);
        Min = 1;
    }

    public int popSmallest() {
    
        int t = Min;
        Hash[Min] = false;

        int left = Min+1;
        while(Hash[left]==false){
    
            left++;
        }
        Min = left;

        return t;
    }

    public void addBack(int num) {
    
        if(Hash[num]==false){
    
            Hash[num] = true;
            if(num<Min) Min = num;
        }
    }
}

Solution 2 ：

Because it is necessary to judge whether it is in the set , use HashSet Sure o(1) Achieve , then PriorityQueue Responsible for taking the minimum value

class SmallestInfiniteSet {
    

    private PriorityQueue<Integer> queue = new PriorityQueue<>();
    private HashSet<Integer> set = new HashSet<>();

    public SmallestInfiniteSet() {
    
        int cnt = 1000;
        for(int i=1;i<=cnt;i++){
    
            set.add(i);
            queue.add(i);
        }
    }

    public int popSmallest() {
    
        int ans = queue.remove();
        set.remove(ans);
        return ans;
    }

    public void addBack(int num) {
    
        if(!set.contains(num)){
    
            set.add(num);
            queue.add(num);
        }
    }
}