Medium

题目描述

你有一个包含所有正整数 [1, 2, 3, 4, 5, …] 的集合。

实现 SmallestInfiniteSet 类：

  • SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象，使其包含所有正整数。
  • int popSmallest() 移除并返回无限集合中包含的最小整数。
  • void addBack(int num) 如果正整数 num 不在无限集合中，则将其添加回无限集合。

示例 1：

输入
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]

解释
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 已经在集合中，所以不做任何改变。
smallestInfiniteSet.popSmallest(); // 返回 1，因为 1 是最小的数字，将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2，将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3，将其从集合中移除。
smallestInfiniteSet.addBack(1);    // 1 被添加回集合中。
smallestInfiniteSet.popSmallest(); // 返回 1，因为 1 被添加回集合，是最小的数字，将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4，将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5，将其从集合中移除。

约束条件：

  • 1 <= num <= 1000
  • 最多总共调用 popSmallest 和 addBack 方法 1000 次。

解题思路

解题思路

这道题的关键在于理解"无限集合"的特性以及如何高效地维护最小值。

核心观察：

  1. 初始集合包含所有正整数 [1, 2, 3, 4, 5, …]
  2. popSmallest 操作会依次移除 1, 2, 3, 4…
  3. addBack 可以将已移除的数字重新加入集合

解法分析：

方法一：最小堆 + 哈希集合

  • 使用最小堆存储被添加回来的数字
  • 维护一个指针 current 表示下一个未被移除的连续正整数
  • 用哈希集合记录已被添加回来的数字，避免重复

方法二：有序集合

  • 直接用有序集合维护所有可用的数字
  • 但这种方法空间复杂度较高

推荐解法：方法一（最小堆 + 指针）

实现细节：

  1. popSmallest：比较堆顶和 current，返回较小值
  2. addBack：如果数字小于 current 且不在堆中，则加入堆
  3. 使用哈希集合快速判断数字是否已在堆中

代码实现

class SmallestInfiniteSet {
private:
    priority_queue<int, vector<int>, greater<int>> minHeap;
    unordered_set<int> inHeap;
    int current;
    
public:
    SmallestInfiniteSet() {
        current = 1;
    }
    
    int popSmallest() {
        if (!minHeap.empty() && minHeap.top() < current) {
            int smallest = minHeap.top();
            minHeap.pop();
            inHeap.erase(smallest);
            return smallest;
        } else {
            return current++;
        }
    }
    
    void addBack(int num) {
        if (num < current && inHeap.find(num) == inHeap.end()) {
            minHeap.push(num);
            inHeap.insert(num);
        }
    }
};

import heapq

class SmallestInfiniteSet:

    def __init__(self):
        self.min_heap = []
        self.in_heap = set()
        self.current = 1

    def popSmallest(self) -> int:
        if self.min_heap and self.min_heap[0] < self.current:
            smallest = heapq.heappop(self.min_heap)
            self.in_heap.remove(smallest)
            return smallest
        else:
            self.current += 1
            return self.current - 1

    def addBack(self, num: int) -> None:
        if num < self.current and num not in self.in_heap:
            heapq.heappush(self.min_heap, num)
            self.in_heap.add(num)

public class SmallestInfiniteSet {
    private PriorityQueue<int, int> minHeap;
    private HashSet<int> inHeap;
    private int current;

    public SmallestInfiniteSet() {
        minHeap = new PriorityQueue<int, int>();
        inHeap = new HashSet<int>();
        current = 1;
    }
    
    public int PopSmallest() {
        if (minHeap.Count > 0 && minHeap.Peek() < current) {
            int smallest = minHeap.Dequeue();
            inHeap.Remove(smallest);
            return smallest;
        } else {
            return current++;
        }
    }
    
    public void AddBack(int num) {
        if (num < current && !inHeap.Contains(num)) {
            minHeap.Enqueue(num, num);
            inHeap.Add(num);
        }
    }
}

var SmallestInfiniteSet = function() {
    this.current = 1;
    this.addedBack = new Set();
};

SmallestInfiniteSet.prototype.popSmallest = function() {
    if (this.addedBack.size > 0) {
        const min = Math.min(...this.addedBack);
        this.addedBack.delete(min);
        return min;
    }
    return this.current++;
};

SmallestInfiniteSet.prototype.addBack = function(num) {
    if (num < this.current) {
        this.addedBack.add(num);
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(1)O(1)
popSmallestO(log k)O(k)
addBackO(log k)O(k)

其中 k 是被添加回集合的元素个数，最多为 1000。

相关题目