题目描述
实现一个数据结构支持以下操作:
Inc(key)
- 插入一个新的值为 1 的key
。或者使一个存在的key
增加 1,保证key
不为空字符串。Dec(key)
- 如果这个key
的值是 1,那么把他从数据结构中移除掉。否者使一个存在的key
值减 1。如果这个key
不存在,这个函数不做任何事情。key
保证不为空字符串。GetMaxKey()
- 返回key
中值最大的任意一个。如果没有元素存在,返回一个空字符串""
。GetMinKey()
- 返回key
中值最小的任意一个。如果没有元素存在,返回一个空字符串""
。
挑战:以 $O(1)$ 的时间复杂度实现所有操作。
算法
(哈希表,双向链表) $O(1)$
- 定义结构体
Node
,记录值value
和所有等于该值的字符串集合。 - 维护一个哈希表,每个
key
对应的一个Node
类型的指针。 Node
结构按值的顺序组成双向链表。初始时有值为 0 和值为INT_MAX
的两个哨兵结点。- 对于插入操作,如果哈希表中不存在,则在哈希表中添加
h[key] = st
。从哈希表中取出当前结构体,将这个key
添加到下一个结构体中(如果不存在则新建立结点),并在当前结构体中删除key
。 - 对于删除,同理进行移动
key
的操作。 - 取最大最小值时,直接取链表的头或尾所对应的的字符串集合。
时间复杂度
- 每次插入或删除只需要常数的时间移动一个
key
。 - 每次询问只需要查看一个结构体。
- 故单次操作或询问的时间复杂度为 $O(1)$。
空间复杂度
- 需要额外的空间存储哈希表以及结构体,故总空间复杂度为 $O(n)$。
C++ 代码
class AllOne {
public:
/** Initialize your data structure here. */
struct Node {
Node *pre, *nxt;
int value;
unordered_set<string> keys;
Node(int v) {
pre = nxt = NULL;
value = v;
}
};
unordered_map<string, Node*> h;
Node *st, *ed;
AllOne() {
st = new Node(0);
ed = new Node(INT_MAX);
st->nxt = ed;
ed->pre = st;
}
void insert(Node *cur, int value) {
Node *nd = new Node(value);
nd->nxt = cur->nxt;
nd->pre = cur;
nd->nxt->pre = nd;
cur->nxt = nd;
}
void remove(Node *cur) {
cur->pre->nxt = cur->nxt;
cur->nxt->pre = cur->pre;
delete cur;
}
/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if (h.find(key) == h.end())
h[key] = st;
Node *cur = h[key];
if (cur->nxt->value > cur->value + 1)
insert(cur, cur->value + 1);
h[key] = cur->nxt;
cur->nxt->keys.insert(key);
if (cur->value > 0) {
cur->keys.erase(key);
if (cur->keys.empty())
remove(cur);
}
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if (h.find(key) == h.end())
return;
Node *cur = h[key];
if (cur->pre->value < cur->value - 1)
insert(cur->pre, cur->value - 1);
if (cur->value > 1) {
h[key] = cur->pre;
cur->pre->keys.insert(key);
} else {
h.erase(key);
}
cur->keys.erase(key);
if (cur->keys.empty())
remove(cur);
}
/** Returns one of the keys with maximal value. */
string getMaxKey() {
if (ed->pre == st)
return "";
return *(ed->pre->keys.begin());
}
/** Returns one of the keys with Minimal value. */
string getMinKey() {
if (st->nxt == ed)
return "";
return *(st->nxt->keys.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();
*/