2336. 无限集中的最小数字

2336. 无限集中的最小数字

• 难度: medium
• 原始链接: https://leetcode.cn/problems/smallest-number-in-infinite-set
• 标签: 有序哈希, 优先级队列

解法一: 有序哈希

java

class SmallestInfiniteSet {

    private TreeSet<Integer> treeSet;

    public SmallestInfiniteSet() {
        treeSet = new TreeSet<>();
        for (int i = 1; i <= 1000; i++) {
            treeSet.add(i);
        }
    }

    public int popSmallest() {
        return treeSet.pollFirst();
    }

    public void addBack(int num) {
        treeSet.add(num);
    }
    
}

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

解法二: 优先级队列

java

class SmallestInfiniteSet {

    private PriorityQueue<Integer> priorityQueue;

    private boolean[] exists;

    private int min;

    public SmallestInfiniteSet() {
        priorityQueue = new PriorityQueue<>((num1, num2) -> num1 - num2);
        min = 1;
        exists = new boolean[1001];
    }

    public int popSmallest() {
        if (!priorityQueue.isEmpty() && exists[priorityQueue.peek()]) {
            Integer ans = priorityQueue.poll();
            exists[ans] = false;
            return ans;
        }
        return min++;
    }

    public void addBack(int num) {
        if (num < min && !exists[num]) {
            priorityQueue.offer(num);
            exists[num] = true;
        }
    }

}

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