实现一个数据结构支持以下操作：
Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
挑战：以 O(1) 的时间复杂度实现所有操作。
思路：
这好像是桶排序吧。
1.以出现次数为key创建桶链表，每个桶内装有所有出现次数为某个值的变量，每个key代表一个桶。
2.以输入的string为key创建哈希表，value为对应的桶。
实现代码如下。
class AllOne {
public:
/** Initialize your data structure here. */
AllOne() {
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if(!hashmap.count(key))
{
if(buckets.empty() || buckets.back().val!=1)
{
auto currBucket=buckets.insert(buckets.end(),{1,{key}});
hashmap[key]=currBucket;
}
else
{
auto currBucket=--buckets.end();
currBucket->keys.insert(key);
hashmap[key]=currBucket;
}
}
else
{
auto currBucket=hashmap[key];
if(currBucket==buckets.begin())
{
auto newBucket=buckets.insert(currBucket,{currBucket->val+1,{key}});
hashmap[key]=newBucket;
}
else
{
auto lastBucket=--hashmap[key];
if(lastBucket->val!=currBucket->val+1)
{
auto newBucket=buckets.insert(currBucket,{currBucket->val+1,{key}});
hashmap[key]=newBucket;
}
else
{
lastBucket->keys.insert(key);
hashmap[key]=lastBucket;
}
}
currBucket->keys.erase(key);
if(currBucket->keys.empty())
{
buckets.erase(currBucket);
}
}
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if(hashmap.count(key))
{
auto currBucket=hashmap[key];
if(currBucket->val==1)
{
currBucket->keys.erase(key);
if(currBucket->keys.empty())
{
buckets.erase(currBucket);
}
hashmap.erase(key);
return;
}
else
{
auto nextBucket=++hashmap[key];
if(nextBucket==buckets.end() || nextBucket->val!=currBucket->val-1)
{
auto newBucket=buckets.insert(nextBucket,{currBucket->val-1,{key}});
hashmap[key]=newBucket;
currBucket->keys.erase(key);
}
else
{
nextBucket->keys.insert(key);
hashmap[key]=nextBucket;
currBucket->keys.erase(key);
}
}
if(currBucket->keys.empty())
{
buckets.erase(currBucket);
}
}
}
/** Returns one of the keys with maximal value. */
string getMaxKey() {
return buckets.empty()?"":*(buckets.begin()->keys.begin());
}
/** Returns one of the keys with Minimal value. */
string getMinKey() {
return buckets.empty()?"":*(buckets.rbegin()->keys.begin());
}
private:
struct bucket{
int val;
unordered_set<string> keys;
};
list<bucket> buckets;
unordered_map<string,list<bucket>::iterator> hashmap;
};
/**
* 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();
*/
