LeetCode-432 全O(1)的数据结构

简介: LeetCode-432 全O(1)的数据结构

来源:力扣(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();
*/

运行结果

 

相关文章
|
2月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
85 0
|
2月前
力扣(LeetCode)数据结构练习题(2)
力扣(LeetCode)数据结构练习题(2)
31 0
|
2月前
|
存储
力扣(LeetCode)数据结构练习题
力扣(LeetCode)数据结构练习题
53 0
|
7月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
53 1
|
7月前
|
算法
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)(下)
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)
22 1
|
7月前
|
算法 C++
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)(上)
数据结构与算法⑮(第四章_下)二叉树OJ(力扣:144,965,104,110,226,100,101,572)
24 1
|
6月前
|
存储 算法 大数据
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
|
7月前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
57 0
|
7月前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
52 0
|
7月前
|
算法 API DataX
二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”
二叉树(下)+Leetcode每日一题——“数据结构与算法”“对称二叉树”“另一棵树的子树”“二叉树的前中后序遍历”