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

Hard

题目描述

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

实现 AllOne 类：

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

注意：每个函数都应当具有 O(1) 的平均时间复杂度。

示例 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 * 10^4 次

解题思路

这道题要求所有操作都要在 O(1) 时间复杂度内完成，需要巧妙的数据结构设计。

核心思路： 使用双向链表 + 哈希表的组合。双向链表的每个节点代表一个计数值，节点内部存储所有具有该计数的字符串集合。

数据结构设计：

双向链表节点：存储计数值和该计数对应的字符串集合
字符串到节点的映射：哈希表记录每个字符串对应的链表节点
计数到节点的映射：哈希表记录每个计数值对应的链表节点

操作实现：

inc(key)：如果key不存在，加入计数1的节点；如果存在，从当前节点移到下一个计数的节点
dec(key)：从当前节点移到前一个计数的节点，如果计数变为0则删除
getMaxKey()：返回链表尾节点中任意一个字符串
getMinKey()：返回链表头节点中任意一个字符串

当节点的字符串集合为空时，需要从链表中删除该节点，保证链表中只有非空的计数节点。

这样设计确保了所有操作都能在常数时间内完成。

代码实现

class AllOne {
private:
    struct Node {
        int count;
        unordered_set<string> keys;
        Node* prev;
        Node* next;
        Node(int c = 0) : count(c), prev(nullptr), next(nullptr) {}
    };
    
    Node* head;
    Node* tail;
    unordered_map<string, Node*> keyToNode;
    unordered_map<int, Node*> countToNode;
    
    void addNode(Node* node, Node* after) {
        node->next = after->next;
        node->prev = after;
        after->next->prev = node;
        after->next = node;
    }
    
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
    }

public:
    AllOne() {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }
    
    void inc(string key) {
        if (keyToNode.find(key) == keyToNode.end()) {
            if (countToNode.find(1) == countToNode.end()) {
                Node* newNode = new Node(1);
                countToNode[1] = newNode;
                addNode(newNode, head);
            }
            countToNode[1]->keys.insert(key);
            keyToNode[key] = countToNode[1];
        } else {
            Node* curNode = keyToNode[key];
            int count = curNode->count;
            
            if (countToNode.find(count + 1) == countToNode.end()) {
                Node* newNode = new Node(count + 1);
                countToNode[count + 1] = newNode;
                addNode(newNode, curNode);
            }
            
            countToNode[count + 1]->keys.insert(key);
            keyToNode[key] = countToNode[count + 1];
            
            curNode->keys.erase(key);
            if (curNode->keys.empty()) {
                countToNode.erase(count);
                removeNode(curNode);
            }
        }
    }
    
    void dec(string key) {
        Node* curNode = keyToNode[key];
        int count = curNode->count;
        
        curNode->keys.erase(key);
        keyToNode.erase(key);
        
        if (count > 1) {
            if (countToNode.find(count - 1) == countToNode.end()) {
                Node* newNode = new Node(count - 1);
                countToNode[count - 1] = newNode;
                addNode(newNode, curNode->prev);
            }
            countToNode[count - 1]->keys.insert(key);
            keyToNode[key] = countToNode[count - 1];
        }
        
        if (curNode->keys.empty()) {
            countToNode.erase(count);
            removeNode(curNode);
        }
    }
    
    string getMaxKey() {
        if (tail->prev == head) return "";
        return *(tail->prev->keys.begin());
    }
    
    string getMinKey() {
        if (head->next == tail) return "";
        return *(head->next->keys.begin());
    }
};

class AllOne:

    def __init__(self):
        class Node:
            def __init__(self, count=0):
                self.count = count
                self.keys = set()
                self.prev = None
                self.next = None
        
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        
        self.key_to_node = {}
        self.count_to_node = {}
    
    def _add_node(self, node, after):
        node.next = after.next
        node.prev = after
        after.next.prev = node
        after.next = node
    
    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def inc(self, key: str) -> None:
        if key not in self.key_to_node:
            if 1 not in self.count_to_node:
                new_node = type(self).Node(1)
                self.count_to_node[1] = new_node
                self._add_node(new_node, self.head)
            
            self.count_to_node[1].keys.add(key)
            self.key_to_node[key] = self.count_to_node[1]
        else:
            cur_node = self.key_to_node[key]
            count = cur_node.count
            
            if count + 1 not in self.count_to_node:
                new_node = type(self).Node(count + 1)
                self.count_to_node[count + 1] = new_node
                self._add_node(new_node, cur_node)
            
            self.count_to_node[count + 1].keys.add(key)
            self.key_to_node[key] = self.count_to_node[count + 1]
            
            cur_node.keys.remove(key)
            if not cur_node.keys:
                del self.count_to_node[count]
                self._remove_node(cur_node)

    def dec(self, key: str) -> None:
        cur_node = self.key_to_node[key]
        count = cur_node.count
        
        cur_node.keys.remove(key)
        del self.key_to_node[key]
        
        if count > 1:
            if count - 1 not in self.count_to_node:
                new_node = type(self).Node(count - 1)
                self.count_to_node[count - 1] = new_node
                self._add_node(new_node, cur_node.prev)
            
            self.count_to_node[count - 1].keys.add(key)
            self.key_to_node[key] = self.count_to_node[count - 1]
        
        if not cur_node.keys:
            del self.count_to_node[count]
            self._remove_node(cur_node)

    def getMaxKey(self) -> str:
        if self.tail.prev == self.head:
            return ""
        return next(iter(self.tail.prev.keys))

    def getMinKey(self) -> str:
        if self.head.next == self.tail:
            return ""
        return next(iter(self.head.next.keys))

public class AllOne {
    
    private class Node {
        public int count;
        public HashSet<string> keys;
        public Node prev;
        public Node next;
        
        public Node(int c = 0) {
            count = c;
            keys = new HashSet<string>();
            prev = null;
            next = null;
        }
    }
    
    private Node head;
    private Node tail;
    private Dictionary<string, Node> keyToNode;
    private Dictionary<int, Node> countToNode;
    
    private void AddNode(Node node, Node after) {
        node.next = after.next;
        node.prev = after;
        after.next.prev = node;
        after.next = node;
    }
    
    private void RemoveNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public AllOne() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
        keyToNode = new Dictionary<string, Node>();
        countToNode = new Dictionary<int, Node>();
    }
    
    public void Inc(string key) {
        if (!keyToNode.ContainsKey(key)) {
            if (!countToNode.ContainsKey(1)) {
                Node newNode = new Node(1);
                countToNode[1] = newNode;
                AddNode(newNode, head);
            }
            countToNode[1].keys.Add(key);
            keyToNode[key] = countToNode[1];
        } else {
            Node curNode = keyToNode[key];
            int count = curNode.count;
            
            if (!countToNode.ContainsKey(count + 1)) {
                Node newNode = new Node(count + 1);
                countToNode[count + 1] = newNode;
                AddNode(newNode, curNode);
            }
            
            countToNode[count + 1].keys.Add(key);
            keyToNode[key] = countToNode[count + 1];
            
            curNode.keys.Remove(key);
            if (curNode.keys.Count == 0) {
                countToNode.Remove(count);
                RemoveNode(curNode);
            }
        }
    }
    
    public void Dec(string key) {
        Node curNode = keyToNode[key];
        int count = curNode.count;
        
        curNode.keys.Remove(key);
        keyToNode.Remove(key);
        
        if (count > 1) {
            if (!countToNode.ContainsKey(count - 1)) {
                Node newNode = new Node(count - 1);
                countToNode[count - 1] = newNode;
                AddNode(newNode, curNode.prev);
            }
            countToNode[count - 1].keys.Add(key);
            keyToNode[key] = countToNode[count - 1];
        }
        
        if (curNode.keys.Count == 0) {
            countToNode.Remove(count);
            RemoveNode(curNode);
        }
    }
    
    public string GetMaxKey() {
        if (tail.prev == head) return "";
        return tail.prev.keys.First();
    }
    
    public string GetMinKey() {
        if (head.next == tail) return "";
        return head.next.keys.First();
    }
}

var AllOne = function() {
    class Node {
        constructor(count = 0) {
            this.count = count;
            this.keys = new Set();
            this.prev = null;
            this.next = null;
        }
    }
    
    this.head = new Node();
    this.tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = this.head;
    
    this.keyToNode = new Map();
    this.countToNode = new Map();
    
    this.addNode = function(node, after) {
        node.next = after.next;
        node.prev = after;
        after.next.prev = node;
        after.next = node;
    };
    
    this.removeNode = function(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    };
};

AllOne.prototype.inc = function(key) {
    if (!this.keyToNode.has(key)) {
        if (!this.countToNode.has(1)) {
            const newNode = new (class Node {
                constructor(count = 0) {
                    this.count = count;
                    this.keys = new Set();
                    this.prev = null;
                    this.next = null;
                }
            })(1);
            this.countToNode.set(1, newNode);
            this.addNode(newNode, this.head);
        }
        this.countToNode.get(1).keys.add(key);

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析