題目

實現一個資料結構，能支持下面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;
    }
};