LeetCode刷题实战432：全 O(1) 的数据结构-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 全 O(1) 的数据结构，我们先来看题面：

https://leetcode-cn.com/problems/all-oone-data-structure/

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

AllOne() Initializes the object of the data structure.

inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.

dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.

getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".

getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

请你实现一个数据结构支持以下操作：

Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串"" 。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。

解题

思路：

https://www.jianshu.com/p/1a850457014c

有点像是桶排序

1.以出现次数为key创建桶链表，每个桶内装有所有出现次数为某个值的变量，每个key代表一个桶。

2.以输入的string为key创建哈希表，value为对应的桶。

实现代码如下。

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

class AllOne {
public:
    /** Initialize your data structure here. */
    AllOne() {
        
    }
    
    /** Inserts a new 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 buckets;
    unordered_map<string,list::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();
 */