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();
*/
运行结果
最新文章
- python编码规范
- web自动化测试中绕开验证码登陆的方式
- java 如何在pdf中生成表格
- 获取jsp页面的宽和高
- Oracle logmnr工具分析日志脚本
- AVL树(二)之 C++的实现
- Node.js Web框架收集
- linux下如何不编译opencv的某些模块
- 四 AndEngine 画线
- sybase下convert函数第三个参数（时间格式）
- 未能解析目标框架“.NETFramework,Version=v4.0”的 mscorlib 错误的解决办法
- 解决SQL server不支持utf8，php却用utf8的矛盾问题
- 手机号ID开关星号(*)
- C#制作高仿360安全卫士窗体2
- C#表达式和语句
- Linux内存映射--mmap函数
- ORACLE 博客文章目录
- Version Control/Git，SVN
- Spring 注解（一）Spring 注解编程模型
- Java之List使用场景