无限集中的最小数字

难度:

标签:

题目描述

代码结果

运行时间: 68 ms, 内存: 17.0 MB

/*
 * 题目思路：
 * - 使用 Java Stream 和集合来管理整数集合。
 * - 使用 TreeSet 保证集合内元素有序，并方便操作最小元素。
 * - 使用过滤和排序操作实现 addBack 和 popSmallest 的功能。
 */
import java.util.Set;
import java.util.TreeSet;

public class SmallestInfiniteSet {
    private TreeSet<Integer> set;
    private int current;

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

    public int popSmallest() {
        if (!set.isEmpty()) {
            return set.pollFirst();
        }
        return current++;
    }

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

解释

方法:

这个题解使用了一个整数val来记录当前未被移除的最小整数，以及一个最小堆lst来存储被重新加入的数字。初始化时，val设置为0，lst为空。当调用popSmallest()时，如果lst非空，则从lst中移除并返回最小元素；如果lst为空，则直接返回val并增加val。对于addBack(num)，只有当num小于等于val且不在lst中时，才将num加入lst。这确保了所有被加回的数字都是之前被移除的数字。

时间复杂度:

O(log n)

空间复杂度:

O(n)

代码细节讲解

🦆

在`SmallestInfiniteSet`类的构造函数中，`self.val`被初始化为0，而不是预期的1。这会如何影响`popSmallest`方法的行为和返回的结果？

▷

初始化`self.val`为0而不是1会导致第一次调用`popSmallest()`方法时返回0，这与预期从1开始返回最小整数不符。这意味着整个数集的起始点被错误地设置为0。这种偏差将使得所有后续的数字也相应地偏移，每个数字都比预期小1。

🦆

对于`addBack`方法，为什么选择只在`num <= self.val`且`num`不在`lst`中时才添加`num`到`lst`？这样的条件判断有什么特定的目的吗？

▷

这样的条件判断确保只有已经被`popSmallest()`方法移除且未被再次移除的数字才能被重新加入。`num <= self.val`确保添加的数字是在当前最小值`self.val`之前的，即它们是之前已经被访问过的。同时，检查`num`是否已在`lst`中可以避免重复添加相同的数字，这有助于保持`lst`的正确性和最小堆的性能。

🦆

在`popSmallest`方法中，当`lst`为空且直接返回`self.val`后增加`self.val`的值，这种操作是否能保证每次都返回集合中当前最小的整数？

▷

是的，这种操作可以保证每次都返回集合中当前最小的整数。当`lst`为空时，`self.val`记录了下一个未被移除的最小整数。返回`self.val`并随后增加其值可以确保连续调用`popSmallest()`时能够依次返回递增的最小整数。只有当`lst`不为空时，这个逻辑才会检查堆中是否有更小的、先前被移除但又被加回的数字。

🦆

题解提到使用最小堆来维护`lst`，这种数据结构选择对于`addBack`和`popSmallest`方法的效率有何影响？

▷

使用最小堆维护`lst`可以高效地支持这两个操作。对于`popSmallest`方法，最小堆能够在常数时间O(1)内提供最小值，并且可以在对数时间O(log n)内移除最小值。对于`addBack`方法，最小堆可以在对数时间O(log n)内插入新元素。这样的时间复杂度是非常适合频繁进行这两种操作的场景，确保了整体操作的效率。

无限集中的最小数字

题目描述

代码结果

解释

代码细节讲解

相关问题