Leetcode-6130: designing digital container systems

subject

Topic linking

Design a digital container system , The following functions can be realized ：

• Given the subscript in the system Insert perhaps Replace A number .
• return The minimum subscript of a given number in the system .

Please realize a NumberContainers class ：

• NumberContainers() Initialize the digital container system .
• void change(int index, int number) In subscript index Fill in number . If the subscript index There are already numbers at , Then use number Replace this number .
• int find(int number) Returns the given number number The minimum subscript in the system . If there is no number , Then the return -1 .

Example ：

 Input ：
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
 Output ：
[null, -1, null, null, null, null, 1, null, 2]

 explain ：
NumberContainers nc = new NumberContainers();
nc.find(10); //  There are no numbers  10 , So back  -1 .
nc.change(2, 10); //  The subscript in the container is  2  Fill in the number  10 .
nc.change(1, 10); //  The subscript in the container is  1  Fill in the number  10 .
nc.change(3, 10); //  The subscript in the container is  3  Fill in the number  10 .
nc.change(5, 10); //  The subscript in the container is  5  Fill in the number  10 .
nc.find(10); //  Numbers  10  Where the subscript is  1 ,2 ,3  and  5 . Because the minimum subscript is  1 , So back  1 .
nc.change(1, 20); //  The subscript in the container is  1  Fill in the number  20 . Be careful , Subscript  1  Before  10 , Now it is replaced by  20 .
nc.find(10); //  Numbers  10  The subscript is  2 ,3  and  5 . The minimum subscript is  2 , So back  2 .

Problem solving

Method 1 ： Hash map+ Ordered set set

establish Numbers —> Indexes Hash map, So when searching , You can find it directly
What if we get the smallest index ？ You can use ordered sets set, that set.begin() The element pointed to is the smallest index .
So build unordered_map<int,set<int>> , Can stabilize O(1) Complexity complete search

class NumberContainers {
    
public:
    unordered_map<int,int> index2num;// Indexes ---> Numbers 
    unordered_map<int,set<int>> num2index;// Numbers ---> Indexes 
    NumberContainers() {
    
    }

    void change(int index, int number) {
    
        if(index2num.count(index)==0){
    
            // Newly inserted index , Directly establish map Just go .
            index2num[index]=number;
            num2index[number].insert(index);
        }else{
    // If the index existed before 
            // Delete the old index first 
            int oldNum=index2num[index];
            num2index[oldNum].erase(index);
            if(num2index[oldNum].empty()){
    
                num2index.erase(oldNum);
            }
            // Insert new index 
            index2num[index]=number;
            num2index[number].insert(index);
        }

    }
    
    int find(int number) {
    
        if(num2index.count(number)){
    
            return *num2index[number].begin();
        }
        return -1;
        
    }
};