来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-oone-data-structure
题目描述
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 AllOne 类：
AllOne() 初始化数据结构的对象。 inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。 dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。 getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。 getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。 示例： 输入 ["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 <= key.length <= 10 key 由小写英文字母组成 测试用例保证：在每次调用 dec 时，数据结构中总存在 key 最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 104 次
解题思路
题目难点在于要将操作的时间复杂度全部变为O(1)，对于修改来说，很容易想到哈希表，但是哈希表的查询最大值最小值的时间复杂度并不是O(1)，查询最大值和最小值的时间复杂度为O(1)的很容易想到优先队列，但是优先队列的修改时间复杂度并不是O(1),所以，这里使用一个递增的双向链表来记录所有数据，当查询最小值返回链表头，查询最大值返回链表尾，并且通过哈希表将链表结点和key值绑定，使得修改时候可以在O(1)时间内找到结点，结点内容存储的是一个set，这样可以将相同计数的结点合成一个结点，将修改的过程缩短到O(1)的时间复杂度。注意在修改时候，分类处理未出现过的key和已出现的key，还有计数为0的key。
代码展示
class AllOne { public: list<pair<unordered_set<string>, int>> NodeList; unordered_map<string, list<pair<unordered_set<string>, int>>::iterator> mapstriterMap; AllOne() { } void inc(string key) { if(mapstriterMap.count(key)) { auto curIter = mapstriterMap[key]; auto nextIter = next(curIter); if(nextIter == NodeList.end() || curIter->second + 1 < nextIter->second) { unordered_set<string> node{key}; mapstriterMap[key] = NodeList.emplace(nextIter, node, curIter->second + 1); } else { nextIter->first.emplace(key); mapstriterMap[key] = nextIter; } curIter->first.erase(key); if(curIter->first.empty()) NodeList.erase(curIter); } else { if(NodeList.empty() || NodeList.begin()->second != 1) { unordered_set<string> node{key}; NodeList.emplace_front(node, 1); } else { NodeList.begin()->first.emplace(key); } mapstriterMap[key] = NodeList.begin(); } } void dec(string key) { if(mapstriterMap.count(key)) { auto curIter = mapstriterMap[key]; auto prevIter = prev(curIter); if(curIter == NodeList.begin()) { if(curIter->second - 1 <= 0) { mapstriterMap.erase(key); } else { unordered_set<string> node{key}; NodeList.emplace_front(node, curIter->second - 1); mapstriterMap[key] = NodeList.begin(); } } else if(curIter->second - 1 > prevIter->second) { unordered_set<string> node{key}; mapstriterMap[key] = NodeList.emplace(curIter, node, curIter->second - 1); } else { prevIter->first.emplace(key); mapstriterMap[key] = prevIter; } curIter->first.erase(key); if(curIter->first.empty()) NodeList.erase(curIter); } } string getMaxKey() { return NodeList.empty()? "" : *NodeList.rbegin()->first.begin(); } string getMinKey() { return NodeList.empty()? "" : *NodeList.begin()->first.begin(); } }; /** * 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(); */
运行结果
