题目
设计一个数字容器系统，可以实现以下功能：
- 在系统中给定下标处 插入 或者 替换 一个数字。
- 返回 系统中给定数字的最小下标。
请你实现一个 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 。
解题
方法一：哈希map+有序集合set
建立 数字—>索引 的哈希map，这样在查找的时候，就可以直接找到
那么如果取到最小的索引呢？可以使用有序集合set，那么set.begin()指向的元素就是最小的索引。
因此构建 unordered_map> ,可以稳定O(1)复杂度完成查找
class NumberContainers { public: unordered_map<int,int> index2num;//索引--->数字 unordered_map<int,set<int>> num2index;//数字--->索引 NumberContainers() { } void change(int index, int number) { if(index2num.count(index)==0){ //新插入的索引，直接建立map就行。 index2num[index]=number; num2index[number].insert(index); }else{//如果索引之前存在 //先删除旧的索引 int oldNum=index2num[index]; num2index[oldNum].erase(index); if(num2index[oldNum].empty()){ num2index.erase(oldNum); } //插入新的索引 index2num[index]=number; num2index[number].insert(index); } } int find(int number) { if(num2index.count(number)){ return *num2index[number].begin(); } return -1; } };
