设计数字容器系统

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

难度: Medium

设计一个数字容器系统，可以实现以下功能：

  • 在系统中给定下标处 插入 或者 替换 一个数字。
  • 返回 系统中给定数字的最小下标。

请你实现一个 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 次。

Submission

运行时间: 341 ms

内存: 72.1 MB

class NumberContainers:
    def __init__(self):
        self.m = {}
        self.ms = defaultdict(list)

    def change(self, index: int, number: int) -> None:
        self.m[index] = number
        heappush(self.ms[number], index)
        
    def find(self, number: int) -> int:
        h = self.ms[number]
        while h and self.m[h[0]] != number:
            heappop(h)
        return h[0] if h else -1



# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)

Explain

此题解采用了散列表和最小堆的组合来实现数字容器系统。散列表 `m` 用于保存 `index` 和 `number` 的映射，以便在 O(1) 时间内访问或更新任何索引处的数字。另一方面，`ms` 也是一个散列表，但其值是一个最小堆，用于存储每个数字的所有索引。通过最小堆，我们可以快速访问每个数字的最小索引。在 `change` 方法中，每次改变或插入一个数字时，都会更新散列表 `m` 和对应数字的堆。在 `find` 方法中，为了找到某个数字的最小索引，我们检查堆顶元素是否仍然有效（即堆顶索引处的数字与查询的数字匹配），如果不匹配则将堆顶元素弹出，直到堆顶元素有效或堆为空。

时间复杂度: O(log n) for `change`, O(log n) average for `find`, but can degrade to O(n) in worst case

空间复杂度: O(I + N) where I is the number of unique indices and N is the total number of operations

class NumberContainers:
    def __init__(self):
        self.m = {}  # Maps index to number
        self.ms = defaultdict(list)  # Maps number to a min-heap of indices

    def change(self, index: int, number: int) -> None:
        self.m[index] = number  # Update or set the number at the given index
        heappush(self.ms[number], index)  # Push the index into the min-heap for this number

    def find(self, number: int) -> int:
        h = self.ms[number]  # Get the min-heap for this number
        while h and self.m[h[0]] != number:  # Clean up outdated indices
            heappop(h)  # Remove the top element if it's not valid anymore
        return h[0] if h else -1  # Return the smallest valid index or -1 if there are none

Explore

散列表被选用是因为它提供了极快的平均时间复杂度为 O(1) 的访问和更新操作。这对于频繁变更和查询索引对应的数值是非常有效的。虽然像平衡二叉搜索树（如 AVL 树或红黑树）等数据结构也可以用于索引到数字的映射，并且提供 O(log n) 的时间复杂度进行查找、插入和删除操作，但其性能不如散列表。因此，散列表是实现快速访问和更新的首选数据结构。

是的，如果同一个索引被多次更新为不同的数字，最小堆中确实会存在过期的索引。这是因为在`change`方法中，每次更改索引处的数字时，该索引都会被添加到新数字对应的最小堆中，而老的数字在其对应的堆中的索引并没有被移除。这会导致堆中存在一些不再有效的索引，从而在`find`方法中影响性能，因为可能需要多次弹出这些过时的堆顶元素来找到一个有效的最小索引。

在`change`方法中不直接处理过时的堆顶元素是为了保持方法的简单性和高效性。每次在`change`方法中处理过时元素需要持续检查和更新所有相关的堆，这可能会导致每次更改操作的成本增加，特别是在高更新率的应用场景中。相反，将清理操作延迟到`find`方法中可以在不频繁查询时避免不必要的性能开销，只有在真正需要时才清理过时的索引。

原始设计并不支持并发操作，因为散列表和最小堆的操作未加锁，可能会在多线程环境下导致数据竞争和一致性问题。要支持并发，可以通过添加适当的锁来确保线程安全。例如，可以为散列表和每个数字对应的最小堆分别使用读写锁（读多写少场景）或互斥锁（写多场景）。此外，还可以考虑使用并发数据结构，如 Java 中的 ConcurrentHashmap，来代替标准的散列表和堆结构，以自动管理并发操作的复杂性。