Leetcode 6113.无限集中的最小数字

1.问题描述

2.解决方案

解法一：

Hash负责在集合内的标位true，不在的为false，并且在popSmallest和addBack的过程中，动态维护一个最小值

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;
        }
    }
}

解法二：

因为要判断是不是在集合中，用HashSet可以o(1)做到，然后PriorityQueue负责取最小值

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);
        }
    }
}