今日题目

https://leetcode.com/problems/design-a-number-container-system/description/

解题思路

在这道题中，我们需要找到列表中某个数字对应的最小索引。 注意，在处理列表时，索引可能会发生变化。 由于我们需要的是最小索引，因此需要一个有序数据结构。 技巧：我们可以使用懒惰标记，记录每个索引对应的数字，只有当发现当前答案不满足要求时才进行弹出操作。

方法

  1. 维护一个字典，存储每个数字对应的有序索引序列。
  2. 维护一个字典，存储索引与数字的映射关系。
  3. 在 find 函数中验证答案是否有效。

复杂度

  • 时间复杂度：$O(Q\ times log(N))$，Q 为查询次数，N 为字典大小。

  • 空间复杂度：$O(Q)$，Q 为查询次数。

代码

class NumberContainers:

    def __init__(self):
        self.lst = dict()
        self.idx = dict()

    def change(self, index: int, number: int) -> None:
        if number not in self.lst:
            self.lst.update({number: []})

        heappush(self.lst[number], index)
        self.idx.update({index: number})

    def find(self, number: int) -> int:
        if number not in self.lst:
            return -1
        while self.lst[number]:
            currIndex = self.lst[number][0]
            if self.idx[currIndex] != number:
                heappop(self.lst[number])
            else:
                return currIndex
        return -1


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

image.png