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

难度：$hard$

---

题目描述

请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 $AllOne$ 类：

• $AllOne()$ 初始化数据结构的对象。
• $inc(Stringkey)$ 字符串 $key$ 的计数增加 $1$ 。如果数据结构中尚不存在 $key$ ，那么插入计数为 $1$ 的 $key$ 。
• $dec(Stringkey)$ 字符串 $key$ 的计数减少 $1$ 。如果 $key$ 的计数在减少后为 $0$ ，那么需要将这个 $key$ 从数据结构中删除。测试用例保证：在减少计数前，$key$ 存在于数据结构中。
• $getMaxKey()$ 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 $""$ 。
• $getMinKey()$ 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 $""$ 。

注意： 每个函数都应当满足 $O(1)$ 平均时间复杂度。

示例：

输入
["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\ast 10^4$ 次

---

算法

(哈希表，双向链表)

1. 定义结构体 Node，记录值 value 和所有等于该值的字符串集合。
2. 维护一个哈希表，每个 key 对应的一个 Node 类型的指针。
3. Node 结构按值的顺序组成双向链表。初始时有值为 INT_MIN 和值为 INT_MAX 的两个哨兵结点。
4. 对于插入操作，如果哈希表中不存在，则在哈希表中添加 h[key] = new node(val)。从哈希表中取出当前结构体，将这个 key 添加到下一个结构体中（如果不存在则新建立结点），并在当前结构体中删除 key。
5. 对于删除，同理进行移动 key 的操作。
6. 取最大最小值时，直接取链表的头或尾所对应的的字符串集合。

复杂度分析

• 时间复杂度：$O(1)$

• 空间复杂度 : $O(n)$

C++ 代码

class AllOne {
public://创建一个双链表，其中有左右指针struct Node {Node *left, *right;int val;unordered_set<string> S;Node(int _val) {val = _val;left = right = NULL;}}*left, *right;// 创建一个哈希表unordered_map<string, Node*> hash;//初始化双链表最左边的节点和最右边的节点AllOne() {left = new Node(INT_MIN), right = new Node(INT_MAX);right->left = left, left->right = right;}//在节点的右边插入一个新的节点Node* add_to_right(Node *node, string key, int val) {if (node->right->val == val) node->right->S.insert(key);else {auto t = new Node(val);t->S.insert(key);t->right = node->right, node->right->left = t;node->right = t, t->left = node;}return node->right;}//在节点的左边边插入一个新的节点Node* add_to_left(Node *node, string key, int val) {if (node->left->val == val) node->left->S.insert(key);else {auto t = new Node(val);t->S.insert(key);t->left = node->left, node->left->right = t;node->left = t, t->right = node;}return node->left;}//删除一个节点void remove(Node* node) {node->left->right = node->right;node->right->left = node->left;delete node;}void inc(string key) {//如果该节点计数为0,在最左边插入一个值为1的节点if (hash.count(key) == 0) hash[key] = add_to_right(left, key, 1);else {//向右插入一个新的节点auto t = hash[key];t->S.erase(key);hash[key] = add_to_right(t, key, t->val + 1);if (t->S.empty()) remove(t);}}void dec(string key) {if (hash.count(key) == 0) return;auto t = hash[key];t->S.erase(key);if (t->val > 1) {hash[key] = add_to_left(t, key, t->val - 1);} else {hash.erase(key);}if (t->S.empty()) remove(t);}string getMaxKey() {if (right->left != left) return *right->left->S.begin();return "";}string getMinKey() {if (left->right != right) return *left->right->S.begin();return "";}
};/*** 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();*/

---

修改变量版本：

class AllOne {
public:struct Node {Node *pre, *nxt;int value;unordered_set<string> keys;Node (int val) {value = val;pre = nxt = NULL;}}*left, *right;unordered_map<string, Node*> hash;AllOne() {left = new Node(0);right = new Node(INT_MAX);left->nxt = right;right->pre = left;}Node* add_to_right(Node* node, string key, int val) {if (node->nxt->value == val) node->nxt->keys.insert(key);else {auto t = new Node(val);t->keys.insert(key);t->nxt = node->nxt, node->nxt->pre = t;t->pre = node, node->nxt = t;}return node->nxt;}Node* add_to_left(Node* node, string key, int val) {if (node->pre->value == val) node->pre->keys.insert(key);else {auto t = new Node(val);t->keys.insert(key);node->pre->nxt = t, t->nxt = node;t->pre = node->pre, node->pre = t;}return node->pre;}void remove(Node *node) {node->pre->nxt = node->nxt;node->nxt->pre = node->pre;delete node;}void inc(string key) {if (hash.count(key) == 0) hash[key] = add_to_right(left, key, 1);else {auto t = hash[key];t->keys.erase(key);hash[key] = add_to_right(t, key, t->value + 1);if (t->keys.empty()) remove(t);}}void dec(string key) {if (hash.count(key) == 0) return;auto t = hash[key];t->keys.erase(key);if (t->value > 1) {hash[key] = add_to_left(t, key, t->value - 1);} else {hash.erase(key);}if (t->keys.empty()) remove(t);}string getMaxKey() {if (left->nxt != right) return *right->pre->keys.begin();return "";}string getMinKey() {if (right->pre != left) return *left->nxt->keys.begin();return "";}
};/*** 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();*/