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

题目

请你实现一个数据结构支持以下操作：

• Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
• Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
• GetMaxKey() - 返回 key中值最大的任意一个。如果没有元素存在，返回一个空字符串"" 。
• GetMinKey() - 返回 key中值最小的任意一个。如果没有元素存在，返回一个空字符串""。

题解

双向链表
对于链表的结点规定：有一个值val，且val的大小决定结点的位置，根据val进行排序；有一个key集合，表示当前值的所有key
同时，我们需要用到一个哈希表记录key所在的结点。
插入数据时

• 利用哈希表找是否有这个key
  • 没有，则判断链表首部的val是否为1，不是，则插入一个val=1的结点；否则，则直接把key放入集合中
  • 有，如果是尾节点，我们判断key集合元素个数，如果为1，直接修改val即可；否则，则需要添加一个新的尾节点，同时在原key集合中删除要插入的key；其他情况下，我们判断后面紧挨着的结点是不是val+1，是，则直接将key放到后面结点的key集合中，同时判断是否需要删除原结点；不是的话，如果当前结点key集合只有一个，直接修改val即可，否则则新建一个结点，同时在原key集合中删除要插入的key

删除数据时，利用哈希表找到它所在的结点

• 如果val=1，若key集合只有一个元素，则更新head结点；否则，在key集合中删除即可
• 其他情况下
  • 如果是头结点，如果当前key集合只有一个元素，则更新val即可；否则，则需要新建一个结点，并更新头节点
  • 我们判断前面紧挨着的结点是不是val-1，是，则直接将key放到前面结点的key集合中，同时判断是否需要删除原结点；不是的话，如果当前结点key集合只有一个，直接修改val即可，否则则新建一个结点，同时在原key集合中删除要插入的key
    详细过程见代码

代码

struct Node{unordered_set<string> container;int val;Node* pre;Node* next;Node(string s){pre = NULL;next = NULL;val = 1;container.insert(s);}
};
class AllOne {
public:unordered_map<string,Node*> list;Node* head;Node* tail;/** Initialize your data structure here. */AllOne() {head = NULL;tail = NULL;}/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */void inc(string key) {if(list.count(key)){		//已存在Node* now = list[key];if(now == tail){		//在尾节点中if(now->container.size() == 1)  now->val += 1;		//可以直接修改valelse{		//需要新建一个结点Node* newTail = new Node(key);newTail->val = now->val+1;tail->next = newTail;newTail->pre = tail;tail = newTail;now->container.erase(key);list[key] = tail;}}else{if(now->next->val == now->val+1){		//后面挨着的结点，val+1now->next->container.insert(key);if(now->container.size() == 1){		//原来的结点只有1个元素，需要删除原来的结点if(now == head){now->next->pre = NULL;head = now->next;}else{Node* prev = now->pre;prev->next = now->next;now->next->pre = prev;}}else{now->container.erase(key);}list[key] = now->next;}else{		//后面挨着的不是val+1if(now->container.size() == 1)  now->val += 1;		//可以直接修改valelse{		//新建一个结点Node* newNode = new Node(key);newNode->val = now->val+1;newNode->next = now->next;newNode->pre = now;now->next->pre = newNode;now->next = newNode;now->container.erase(key);list[key] = now->next;}}}}else{		//没有出现if(head==NULL){		//空链表，直接建立结点head = new Node(key);tail = head;}else{if(head->val == 1)  head->container.insert(key);		//头节点val=1，直接插入即可else{		//建立新的头节点Node* newHead = new Node(key);	newHead->next = head;head->pre = newHead;head = newHead;}}list[key] = head;}}/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */void dec(string key) {if(list.count(key)){		Node* now = list[key];if(now->val == 1){		//发生在头结点上if(now->container.size() == 1){		//只有这一个元素，需要删除结点if(tail == head){		//只有这一个结点，删除后，链表为空head = NULL;tail = head;}else{head = head->next;}}else{now->container.erase(key);}list.erase(key);}else if(now == head){		//发生在头节点上if(now->container.size() == 1)  now->val-=1;		//可以直接修改valelse{		//需要新建一个头节点Node* newHead = new Node(key);newHead->val = now->val-1;head->pre = newHead;newHead->next = head;head = newHead;now->container.erase(key);list[key] = head;}}else{		//发生在其他结点上if(now->pre->val == now->val-1){		//前面紧挨着的结点，val-1now->pre->container.insert(key);if(now->container.size() == 1){		//原结点只有一个元素，需要删除原结点Node* prev = now->pre;prev->next = now->next;if(now!=tail) now->next->pre = prev;else tail = prev;}else{now->container.erase(key);}list[key] = now->pre;}else{		//前面挨着的结点，不是val-1if(now->container.size() == 1)  now->val -= 1;	//只有一个元素，可以直接修改val		else{		//建立一个新的结点Node* newNode = new Node(key);newNode->val = now->val-1;newNode->next = now;newNode->pre = now->pre;now->pre->next = newNode;now->pre = newNode;now->container.erase(key);list[key] = now->pre;}}}}}/** Returns one of the keys with maximal value. */string getMaxKey() {if(tail == NULL)    return "";return *(tail->container.begin());}/** Returns one of the keys with Minimal value. */string getMinKey() {if(head == NULL)    return "";return *(head->container.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();*/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-oone-data-structure
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。