题目
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 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 <= key.length <= 10
- key 由小写英文字母组成
- 测试用例保证：在每次调用 dec 时，数据结构中总存在 key
- 最多调用 inc、dec、getMaxKey 和 getMinKey 方法
5
∗
1
0
4
5 * 10^4
5∗104次
思路
很显然由于数据量比较大，所以贪心地遍历会导致时间超限。
这是对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();
*/
