LeetCode 432题:打造全 O(1) 算法的数据结构(创意设计题)
最编程
2024-07-20 15:32:11
...
文章目录
- 1. 题目
- 2. 解题
1. 题目
请你实现一个数据结构支持以下操作:
-
Inc(key)
- 插入一个新的值为 1 的 key。 或者使一个存在的 key 增加一,保证 key 不为空字符串。 -
Dec(key)
- 如果这个 key 的值是 1,那么把他从数据结构中移除掉。 否则使一个存在的 key 值减一。 如果这个 key 不存在,这个函数不做任何事情。key 保证不为空字符串。 -
GetMaxKey()
- 返回 key 中值最大的任意一个。 如果没有元素存在,返回一个空字符串"" 。 -
GetMinKey()
- 返回 key 中值最小的任意一个。 如果没有元素存在,返回一个空字符串""。
挑战: 你能够以 O(1) 的时间复杂度实现所有操作吗?
2. 解题
参考大佬的题解
class node
{
public:
int val;
unordered_set<string> s;
node(int v)
{
val = v;
}
};
class AllOne {
unordered_map<string, list<node>::iterator> m;
list<node> l;
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) {
auto it = m.find(key);
if(it == m.end())
{
if(l.empty() || l.front().val > 1)
l.push_front(node(1));//没有val为1的,新建
l.begin()->s.insert(key);
m[key] = l.begin();
}
else
{
auto iter = it->second;//迭代器位置
int num = iter->val;//当前数字
iter->s.erase(key);//原位置处删除
auto olditer = iter;
auto newiter = ++iter;
num++;
if(newiter != l.end() && newiter->val == num)
{ //新位置数字刚好是+1以后的
newiter->s.insert(key);
m[key] = newiter;
}
else
{ //新开辟节点
auto temp = l.insert(newiter,node(num));//新节点之前插入
temp->s.insert(key);//返回的当前节点存入字符串
m[key] = temp;
}
if(olditer->s.empty())
l.erase(olditer);//原来节点为空要删除
}
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
auto it = m.find(key);
if(it == m.end()) return;
auto iter = it->second;
int num = iter->val;
iter->s.erase(key);
auto olditer = iter;
auto newiter = --iter;
num--;
if(num == 0)
m.erase(key);
else if(olditer != l.begin() && newiter->val == num)
{ //前面还有节点,且数字吻合
newiter->s.insert(key);
m[key] = newiter;
}
else
{ //前面数字不符合,在老节点前插入
auto temp = l.insert(olditer,node(num));
temp->s.insert(key);
m[key] = temp;
}
if(olditer->s.empty())
l.erase(olditer);
}
/** Returns one of the keys with maximal value. */
string getMaxKey() {
if(l.empty()) return "";
return *(l.back().s.begin());
}
/** Returns one of the keys with Minimal value. */
string getMinKey() {
if(l.empty()) return "";
return *(l.front().s.begin());
}
};
100 ms 24.9 MB