leetcode-6130：设计数字容器系统

题目

题目连接

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

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

请你实现一个 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<int,set<int>> ,可以稳定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;
        
    }
};