LeetCode 题解工作台
设计数字容器系统
设计一个数字容器系统，可以实现以下功能： 在系统中给定下标处 插入 或者 替换 一个数字。 返回 系统中给定数字的最小下标。 请你实现一个 NumberContainers 类： NumberContainers() 初始化数字容器系统。 void change(int index, int num…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 堆
答案摘要
我们用一个哈希表 记录下标和数字的映射关系，用一个哈希表 记录每个数字对应的下标集合，这里我们可以使用有序集合来存储下标，这样我们就可以方便地找到最小下标。 调用 `change` 方法时，我们先判断下标是否已经存在，如果存在，我们就将原来的数字从对应的下标集合中删除，然后将新的数字添加到对应的下标集合中。时间复杂度 $O(\log n)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
设计一个数字容器系统，可以实现以下功能：
- 在系统中给定下标处 插入 或者 替换 一个数字。
- 返回 系统中给定数字的最小下标。
请你实现一个 NumberContainers 类：
NumberContainers()初始化数字容器系统。void change(int index, int number)在下标index处填入number。如果该下标index处已经有数字了，那么用number替换该数字。int find(int number)返回给定数字number在系统中的最小下标。如果系统中没有number，那么返回-1。
示例：
输入： ["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"] [[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]] 输出： [null, -1, null, null, null, null, 1, null, 2] 解释： NumberContainers nc = new NumberContainers(); nc.find(10); // 没有数字 10 ，所以返回 -1 。 nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。 nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。 nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。 nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。 nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。 nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。 nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。
提示：
1 <= index, number <= 109- 调用
change和find的 总次数 不超过105次。
解题思路
方法一：哈希表 + 有序集合
我们用一个哈希表 记录下标和数字的映射关系，用一个哈希表 记录每个数字对应的下标集合，这里我们可以使用有序集合来存储下标，这样我们就可以方便地找到最小下标。
调用 change 方法时，我们先判断下标是否已经存在，如果存在，我们就将原来的数字从对应的下标集合中删除，然后将新的数字添加到对应的下标集合中。时间复杂度 。
调用 find 方法时，我们直接返回对应数字的下标集合的第一个元素即可。时间复杂度 。
空间复杂度 。其中 为数字的个数。
class NumberContainers:
def __init__(self):
self.d = {}
self.g = defaultdict(SortedSet)
def change(self, index: int, number: int) -> None:
if index in self.d:
old_number = self.d[index]
self.g[old_number].remove(index)
self.d[index] = number
self.g[number].add(index)
def find(self, number: int) -> int:
ids = self.g[number]
return ids[0] if ids else -1
# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity for change and find is O(log n) because updating or retrieving from a sorted set of indices per number takes logarithmic time. Space complexity is O(n) since we store mappings for each index and for all indices per number. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Check if candidate uses both number-to-indices and index-to-number maps correctly.
- question_mark
Observe whether updates remove indices from previous numbers before insertion.
- question_mark
Watch for correct handling of find when no index exists for a number.
常见陷阱
外企场景- error
Failing to remove an index from the old number's set before updating can produce incorrect find results.
- error
Not using a sorted structure for indices may return the wrong smallest index.
- error
Assuming indices are contiguous leads to inefficient O(n) searches instead of using hash maps.
进阶变体
外企场景- arrow_right_alt
Return all indices for a number instead of just the smallest.
- arrow_right_alt
Support batch updates to multiple indices at once.
- arrow_right_alt
Restrict number ranges to 1-1000 to simplify storage but maintain design logic.