LC.P2336[无限集中的最小数字]

方法一：有序集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class SmallestInfiniteSet {

    TreeSet<Integer> set = new TreeSet<>();

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

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

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

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */
  • 时间复杂度：$O(logn)$
  • 空间复杂度：$O(n)$

方法二：优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class SmallestInfiniteSet {

    TreeSet<Integer> set;
    int idx;

    public SmallestInfiniteSet() {
        set = new TreeSet<>();
        idx = 1;
    }

    public int popSmallest() {
        return set.isEmpty() ? idx++ : set.pollFirst();
    }

    public void addBack(int num) {
        if (num < idx) set.add(num);
    }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */
  • 时间复杂度：$O(logn)$
  • 空间复杂度：$O(n)$