全O(1)的数据结构
题目
实现一个数据结构支持以下操作：
- Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
- Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。 key 保证不为空字符串。
- GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
- GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
挑战：以 O(1) 的时间复杂度实现所有操作。
多重引用
Inc(key)和Dec(key)要以常数时间复杂度按键找到值「计数」并递增或递减。常用数据结构中，散列表「Hash Table」可以实现常数复杂度的按键查找值。如果维持一个有序序列，则GetMaxKey()和GetMinKey()也可以常数复杂度实现。双向链表就可以实现一个有序序列，同时支持常数时间复杂度的元素移除插入。
我们创建一个组合散列表和双向链表的数据结构。其中，散列表指向的是双向链表节点，每个节点除了存储键和计数外，还持有前向和后向引用，分别指向双向链表中的前向和后向节点。
当Inc(key)时，先通过散列表按键找到目标节点，递增计数。再将节点在双向链表中向前移动，直至遇到计数不小于其的节点。
当Dec(key)时，先通过散列表㧒键找到目标节点，递减计数。再将节点在双向链表中向后移动，直至遇到计数不大于其的节点。
GetMakKey()则直接读取双向链表的头节点。
GetMinKey()则直接读取双向链表的尾节点。
举个例子，
inc('A')时，构造一个新的节点，计数为1，存入散列表，同时添加至双向链表尾端。
inc('B')时，构造一个新的节点，计数为1，存入散列表，同时添加至双向链表尾端。
inc('C')时，构造一个新的节点，计数为1，存入散列表，同时添加至双向链表尾端。
inc('B')时，从散列表中读取节点，计数加一，并将其在双向链表中向前移动，直至头部。
dec('A')时，从散列表中读取节点，计数减一。此时计数为0，所以将其从散列表和双向链表中移除。
GetMaxKey()时，直接读取双向链表的头部节点。
GetMinKey()时，直接读取双向链表的尾部节点。
代码实现
package io.github.rscai.leetcode.bytedance.datastructure;
import java.util.HashMap;
import java.util.Map;
public class Solution1033A {
private class Node {
String value;
int count;
Node previous;
Node next;
public Node() {
}
public Node(String value) {
this.value = value;
this.count = 1;
}
public int incCount() {
count++;
return count;
}
public int decCount() {
count--;
return count;
}
}
private static final String NOT_FOUND = "";
private Map<String, Node> data;
private Node head;
private Node tail;
/**
* Initialize your data structure here.
*/
public Solution1033A() {
data = new HashMap<>();
}
/**
* Inserts a new key <Key> with value 1. Or increments an existing key by 1.
*/
public void inc(String key) {
if (data.containsKey(key)) {
Node node = data.get(key);
node.incCount();
adjustOrderIfNeed(node);
} else {
Node node = new Node(key);
data.put(key, node);
addToTail(node);
}
}
/**
* Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
*/
public void dec(String key) {
if (data.containsKey(key)) {
Node node = data.get(key);
node.decCount();
if (node.count == 0) {
data.remove(node.value);
}
adjustOrderIfNeed(node);
}
}
/**
* Returns one of the keys with maximal value.
*/
public String getMaxKey() {
if (head != null) {
return head.value;
} else {
return NOT_FOUND;
}
}
/**
* Returns one of the keys with Minimal value.
*/
public String getMinKey() {
if (tail != null) {
return tail.value;
} else {
return NOT_FOUND;
}
}
private void adjustOrderIfNeed(Node node) {
if (node.count == 0) {
// remove
if (node.previous != null) {
node.previous.next = node.next;
}
if (node.next != null) {
node.next.previous = node.previous;
}
if (head == node) {
head = node.next;
}
if (tail == node) {
tail = node.previous;
}
} else {
Node current = node;
// move forward if node's count greater than previous's
while (current.previous != null && current.previous.count < current.count) {
Node previous = current.previous;
Node previousOfPrevious = previous.previous;
Node next = current.next;
if (next != null) {
next.previous = previous;
}
previous.next = next;
previous.previous = current;
current.next = previous;
current.previous = previousOfPrevious;
if (previousOfPrevious != null) {
previousOfPrevious.next = current;
}
if (head == previous) {
head = current;
}
if (tail == current) {
tail = previous;
}
}
// move backward if node's count less than next's
while (current.next != null && current.next.count > current.count) {
Node previous = current.previous;
Node next = current.next;
Node nextOfNext = next.next;
next.previous = previous;
next.next = current;
if (previous != null) {
previous.next = next;
}
current.next = next.next;
current.previous = next;
if (head == current) {
head = next;
}
if (tail == next) {
tail = current;
}
}
}
}
private void addToTail(Node node) {
if (tail != null) {
tail.next = node;
node.previous = tail;
tail = node;
} else {
tail = node;
head = tail;
}
}
}
定义双向链表的节点，该节点除了持有值和计数外，还持有前向和后向节点的引用。散列表的值类型就为该节点。
inc(key)分两种情况：
- 散列表已含有相同键的。从散列表中取出键对应的节点，将计数加一，并调整其在双向链表中的位置。
- 散列表中未含有相同键。构造一个新的节点，计数设为一，加入散列表，同时添加至双向链表末尾。
dec(key)直接从散列表中取出节点（若其存在于散列表），将计数减一。若此时计数跃至0，则将其从散列移除。但无论如何，都要重新调整其在双向链表中的位置。
双向链表一直将所有节点按计数有序排列。GetMaxKey()直接从头部获取最大值。
GetMinKey()直接从尾部获取最小值。
将节点添至双向链表末尾的操作比较简单。
调整节点在双向链表中的位置时分两种情况：
- 计数为0，直接从链表中移除
- 计数不为0，则向前移动直至遇到计数不小于其的节点或到达头部：向后移动直至遇到计数不大于其的节点或到达尾部。
复杂度分析
时间复杂度
inc(key)调用了HashMap.containsKey, HashMap.get, HashMap.put, adjustOrderIfNeed, addTotail。其中：
HashMap.containsKey是常数时间复杂度操作HashMap.get是常数时间复杂度操作HashMap.put是常数时间复杂度操作adjustOrderIfNeed时间复杂度与双向链表中节点计数重复度相关。假设所有键的计数都不相同或极少相同，则adjustOrderIfNedd的时间复杂度为常数addToTail最多更改三个引用的值
所以，inc(key)的时间复杂度为。
dec(key)调用了HashMap.containsKey, HashMap.get, HashMap.remove, adjustOrderIfneed。
HashMap.containsKey是常数时间复杂度操作HashMap.get是常数时间复杂度操作HashMap.remove是常数时间复杂度操作adjustOrderIfNeed是在所有键的计数都不相同或极少相同的情况下是常数复杂度
所以，dec(key)的时间复杂度为。
GetMaxKey()直接读取双向链表的头元素，时间复杂度为。
GetMinKey()直接读取双向链表的尾元素，时间复杂度为。
空间复杂度
散列表和双向链表都只是存储引用，节点仅有一份。假设键数量为，则总共有个节点。每个节点除了持有键和计数外，遇持有两个引用。所以空间复杂度为。