设计一个数字容器系统-php教程-PHP中文网

设计一个数字容器系统

碧海醫心

发布： 2025-02-09 13:12:12

原创

844人浏览过

设计一个数字容器系统

设计一个高效的数字容器系统，支持以下操作：

插入/替换: 将指定索引处的值替换为新值。如果索引不存在，则插入新值。
查找最小索引: 返回给定数字在容器中出现的最小索引。如果数字不存在，则返回 -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 5
1 5
change 和 find 方法的调用次数最多为 10⁵

提示:

为了高效地实现这个系统，可以使用哈希表来存储每个索引对应的值，以及使用最小堆（优先队列）来跟踪每个数字的最小索引。

解决方案 (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中文网其它相关文章！