LeetCode 2349. 设计数字容器系统（SortedSet）

1. 题目

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

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

请你实现一个 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 <= 10^9
调用 change 和 find 的 总次数 不超过 10^5 次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-a-number-container-system
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• SortedSet 存储 index， 有序

from sortedcontainers import SortedSet
class NumberContainers:

    def __init__(self):
        self.idx2num = {}  # idx ： num
        self.num2idxlist = defaultdict(SortedSet) 
        # num ： [idx ...]

    def change(self, index: int, number: int) -> None:
        if index in self.idx2num:
            num = self.idx2num[index]
            self.idx2num.pop(index)
            self.num2idxlist[num].discard(index)
            if len(self.num2idxlist[num]) == 0:
                self.num2idxlist.pop(num)
        self.num2idxlist[number].add(index)
        self.idx2num[index] = number

    def find(self, number: int) -> int:
        if number in self.num2idxlist:
            return self.num2idxlist[number][0]
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

992 ms 55.6 MB Python3

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！