设计一个高效的数字容器系统，支持以下操作：
插入/替换: 将指定索引处的值替换为新值。如果索引不存在，则插入新值。查找最小索引: 返回给定数字在容器中出现的最小索引。如果数字不存在，则返回 -1。
挑战难度： 中等
相关主题: 哈希表，设计模式，最小堆（优先队列）
示例:
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"][[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
说明:
NumberContainers 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 index 51 number 5change 和 find 方法的调用次数最多为 105
提示:
为了高效地实现这个系统，可以使用哈希表来存储每个索引对应的值，以及使用最小堆（优先队列）来跟踪每个数字的最小索引。
解决方案 (Python):
import heapqclass 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') 用作标记，表示索引已失效。
进一步优化:
为了进一步优化，可以考虑使用更高级的数据结构，例如跳表或其他自平衡树，来替代最小堆，但这会增加代码复杂度。 对于大多数用例，最小堆已经足够高效。
以上就是设计一个数字容器系统的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1284283.html
微信扫一扫 
支付宝扫一扫 
