[数据结构与算法]432. 全 O(1) 的数据结构

题目

请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 AllOne 类：

AllOne() 初始化数据结构的对象。
inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 “” 。
getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 “” 。

示例1

输入
["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
输出
[null, null, null, "hello", "hello", null, "hello", "leet"]

解释
AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "hello"
allOne.inc("leet");
allOne.getMaxKey(); // 返回 "hello"
allOne.getMinKey(); // 返回 "leet"

提示

1. 1 <= key.length <= 10
2. key 由小写英文字母组成
3. 测试用例保证：在每次调用 dec 时，数据结构中总存在 key
4. 最多调用 inc、dec、getMaxKey 和 getMinKey 方法 $5?10^4$次

思路

很显然由于数据量比较大，所以贪心地遍历会导致时间超限。
这是对STL进行运用的题目。C++ STL的基础知识可以点击这里观看。

我的想法是同时维护两个字典（映射）：

unordered_map<string, int>
这个映射存的是每一个字符串的计数值，是一个无序映射。

map<int, unordered_set >
这个是一个从整形映射到无序集合的映射。整形代表了计数值，无序集合是当前该计数值对应的所有字符串的集合。需要注意的是，在这里维护的最小的计数值是1。

有了这两个工具，当我们增加或减少一个字符串的计数值时，只需要维护两个映射即可，注意的是当一个字符串计数值为0时，要删除关于它的映射。最后，由于map是有序的，最大最小值直接返回其起始集合和终点集合中的任意值即可。

代码

class AllOne {
public:
    
    unordered_map<string, int> ma;
    map<int, unordered_set<string> > me;
    AllOne() {
        
    }
    
    void inc(string key) {
        if(ma.find(key) == ma.end())
        {
            ma[key] = 1;
            me[1].insert(key);
        }
        else 
        {
            ma[key] ++;
            me[ma[key]-1].erase(key);
            if(me[ma[key]-1].size()==0)me.erase(ma[key]-1);
            me[ma[key]].insert(key);
        }
        
    }
    
    void dec(string key) {
        ma[key] --;
        if(ma[key] == 0)
        {
            ma.erase(key);
            me[1].erase(key);
            if(me[1].size()==0)me.erase(1);
        }
        else
        {
            me[ma[key]].insert(key);
            me[ma[key]+1].erase(key);
            if(me[ma[key]+1].size()==0)me.erase(ma[key]+1);
        }
    }
    
    string getMaxKey() {
        if(ma.size() == 0)return "";
        else 
        {
            map<int, unordered_set<string> >::reverse_iterator  iter = me.rbegin();
            //unordered_set<string> s = iter->second;
            unordered_set<string>:: iterator it = iter->second.begin();
            //it = s.begin();
            return *it;
        }
        return "";
    }
    
    string getMinKey() {
        
        if(ma.size() == 0)return "";
        else 
        {
            map<int, unordered_set<string> >::iterator  iter = me.begin();
            //unordered_set<string> s = iter->second;
            unordered_set<string>:: iterator it = iter->second.begin();
            //it = s.begin();
            return *it;
        }
        return "";
    }
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */