设计一个高效的数字容器系统，支持以下操作：
- 插入/替换: 将指定索引处的值替换为新值。如果索引不存在，则插入新值。
- 查找最小索引: 返回给定数字在容器中出现的最小索引。如果数字不存在，则返回 -1。
挑战难度： 中等
相关主题: 哈希表，设计模式，最小堆（优先队列）
示例:
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"] [[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
登录后复制
说明:
- NumberContners nc = new NumberContainers(); 创建一个新的数字容器系统。
- nc.find(10); 返回 -1，因为 10 还不存在于容器中。
- 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); 返回 1，因为 1 是 10 在容器中出现的最小索引。
- nc.change(1, 20); 将索引 1 处的值替换为 20。
- nc.find(10); 返回 2，因为 2 现在是 10 在容器中出现的最小索引。
约束:
- 1 5
- 1 5
- change 和 find 方法的调用次数最多为 105
提示:
为了高效地实现这个系统，可以使用哈希表来存储每个索引对应的值，以及使用最小堆（优先队列）来跟踪每个数字的最小索引。
解决方案 (Python):
import heapq class NumberContainers: def __init__(self): self.index_map = {} # index -> number self.number_map = {} # number -> min-heap of indices def change(self, index: int, number: int) -> None: if index in self.index_map: old_number = self.index_map[index] heapq.heapreplace(self.number_map[old_number], float('inf')) #Mark as invalid self.index_map[index] = number if number not in self.number_map: self.number_map[number] = [] heapq.heappush(self.number_map[number], index) def find(self, number: int) -> int: if number not in self.number_map: return -1 while self.number_map[number] and self.number_map[number][0] not in self.index_map or self.index_map[self.number_map[number][0]] != number: heapq.heappop(self.number_map[number]) #Remove invalid index return self.number_map[number][0] if self.number_map[number] else -1
登录后复制
这个Python解决方案使用了heapq模块来实现最小堆，并利用两个字典来高效地进行查找和更新操作。 float(‘inf’) 用作标记，表示索引已失效。
进一步优化:
为了进一步优化，可以考虑使用更高级的数据结构，例如跳表或其他自平衡树，来替代最小堆，但这会增加代码复杂度。 对于大多数用例，最小堆已经足够高效。
以上就是设计一个数字容器系统的详细内容，更多请关注php中文网其它相关文章！
微信扫一扫打赏
支付宝扫一扫打赏
