How can I efficiently solve the Smallest Number in Infinite Set problem?

To solve this problem efficiently, use a combination of a hash table for tracking added back elements and a heap for managing the smallest number.

What is the best way to optimize the popSmallest operation?

Using a heap for the popSmallest operation ensures that the smallest element is always accessible in O(log n) time.

What should I keep in mind while implementing addBack in this problem?

When implementing addBack, make sure to track the number in a hash table and add it back into the heap only if it hasn’t been reinserted already.

What are the time and space complexities of the solution?

The time complexity for both popSmallest and addBack is O(log n), while the space complexity is O(n), where n is the number of operations performed.

How does this problem relate to other heap-based problems?

This problem shares similarities with other heap-based problems, where you need to track and manipulate the smallest or largest element in a set efficiently.

#2336

Medium

auto_awesome堆

LeetCode 题解工作台

无限集中的最小数字

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。实现 SmallestInfiniteSet 类： SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含所有正整数。 int popSmallest() 移除并返回该无…

哈希表设计堆（优先队列）有序集合

题目描述

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

实现 SmallestInfiniteSet 类：

SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含所有正整数。
int popSmallest() 移除并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不存在于无限集中，则将一个 num 添加到该无限集中。

示例：

输入
["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 在上一步中被添加到集合中，
                                   // 且 1 是最小的整数，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。

提示：

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

lightbulb

解题思路

方法一：有序集合 + 模拟

我们注意到，题目中集合的元素范围是 $[1, 1000]$ ，并且我们需要支持的操作有：

popSmallest：弹出集合中的最小元素
addBack：向集合中添加元素

因此，我们可以使用有序集合来模拟，不妨记有序集合为 $s$ ，集合中的元素为 $s_1, s_2, \cdots, s_n$ ，其中 $n$ 为有序集合中的元素个数。本题中 $n \le 1000$ 。

我们在初始化时，将 $[1, 1000]$ 中的所有元素加入有序集合中。时间复杂度 $O(n \times \log n)$ 。

在 popSmallest 操作中，我们只需要弹出有序集合中的第一个元素即可。单次操作时间复杂度 $O(\log n)$ 。

在 addBack 操作中，我们只需要将元素加入有序集合中即可。单次操作时间复杂度 $O(\log n)$ 。

空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class SmallestInfiniteSet:
    def __init__(self):
        self.s = SortedSet(range(1, 1001))

    def popSmallest(self) -> int:
        x = self.s[0]
        self.s.remove(x)
        return x

    def addBack(self, num: int) -> None:
        self.s.add(num)


# Your SmallestInfiniteSet object will be instantiated and called as such:
# obj = SmallestInfiniteSet()
# param_1 = obj.popSmallest()
# obj.addBack(num)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates may struggle with balancing efficient popSmallest and addBack operations.
question_mark
Look for solutions using a combination of data structures, especially heaps and hash tables.
question_mark
Ensure the candidate understands the trade-off between space complexity and operation speed.

warning

常见陷阱

外企场景

error
Overusing brute force methods for tracking elements will lead to inefficiency.
error
Not handling the edge case where a number is popped and then added back multiple times.
error
Failing to optimize for time complexity in popSmallest or addBack, leading to suboptimal performance.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling a larger range of numbers efficiently, where the set grows even more.
arrow_right_alt
Adding additional operations, such as checking if a specific number exists in the set.
arrow_right_alt
Optimizing for worst-case time complexity when the number of operations increases.

help

常见问题

外企场景

继续练习

#2349 设计数字容器系统 #2353 设计食物评分系统 #2424 最长上传前缀