题目

实现一个资料结构，能支持下面4个操作:
执行每个操作，时间复杂度都要求为 O(1)

1. Inc(stirng Key)
   如果此key已在资料结构中，则其value加1，反之则插入此key，而value等於1。
2. Dec(string Key)
   如果此key的value等於1，则从资料结构中删除，如果大於1，将value减1。
   如果此key不存在於资料结构中，则不会做任何事情。
3. GetMaxKey()
   回传value最大的key
   如果没key在资料结构中，则回传 ""
4. GetMinKey()
   回传value最小的key
   如果没key在资料结构中，则回传 ""

Code

class AllOne {
public:
    /** Initialize your data structure here. */
    map<string,int> Data;
    AllOne() {
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        Data[key]++;
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        map<string,int>::iterator index = Data.find(key);
        if(index!=Data.end()){
            if(index->second==1){
                Data.erase(key);
            }
            else{
                index->second--;
            }
        }
        
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if(Data.size() == 0) return "";
        map<string, int>::iterator Max = Data.begin();
        for(map<string,int>::iterator index = Data.begin(); index != Data.end(); index++){
            if(Max->second < index->second) {
                Max = index;
            }
        }
        return Max->first;
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if(Data.size() == 0) return "";
        map<string, int>::iterator Min = Data.begin();
        for(map<string,int>::iterator index = Data.begin(); index != Data.end(); index++){
            if(Min->second > index->second) {
                Min = index;
            }
        }
        return Min->first;
    }
};