题目描述

题目链接

题目分析

find需要可以快速查找到是否存在一个元素的最小下标
还需要根据任意的index插入或修改指定的元素内容
可以使用map，哈希容器
同时也要考虑一个情况，当新增了一个元素，导致另一个元素的最小下标发生改变，
还有一种情况，某个元素替换了另一个元素的某一个Index，需要把index就行移动。
可以考虑建立一个哈希number-{index}集合
这个index集合要支撑两个功能：

1. 快速查找到最小的index
2. 快速查找到指定的index并删除

功能1可以考虑使用堆（priority-queue），但是要查找指定的元素并删除，则需要挨个弹出并修改
结合这两个功能，可以使用set，set的底层就是红黑树，而红黑树本质上也是一个最小堆，其查找速率是O(log_2(N)),比priority-queue的查找要快

代码实现

class NumberContainers {
    unordered_map<int,set<int>> index_mp;//使用一个map来记录最小的index
    unordered_map<int,int> value_mp;//使用一个map来从到value容器

public:
    NumberContainers() {
        
    }
    
    void change(int index, int number) {
        //判断是不是插入
        if(!value_mp.contains(index))//插入新位置
        {
            value_mp.insert({index,number});
        }
        else//指定位置修改
        {
            auto value = value_mp[index]; //需要修改这个value的下标集
            value_mp[index] = number;
            index_mp[value].erase(index);   //删除下标集中的index
        }
        process_insert(index,number);


        
    }
    
    int find(int number) {
        if(index_mp.contains(number) && index_mp[number].size()>0)
        {
            return *index_mp[number].begin();
        }
        return -1;
        
    }

    void process_insert(int index,int number)
    {
        if(find(number)==-1)
        {
            index_mp.insert({number,set<int>()});
        }
        index_mp[number].insert(index);

    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */