Problem 3 Implementation All O(1) data structure
Summary
这道不是让我们keep 时间顺序，这题是大小顺序
变化量为1（因为你每次最多增加1）的顺序模型
对单一Data的每一次操作，导致的变化量至多为1:2D的结构设计
单向排列次序不一定是个consecutive的次序
当走流程的时候，新来一个key，走掉一个key，对于node的操作有很复杂，很可能新增或者删除现有的ListNode
Node - Node - Node Freq2- Freq3 - Freq5
横向链接
DLL + Map
对于所有变化量为1的reference Node我们可以实现对数量排序 + 所有对reference operation O(1)
纵向链接
对于同样横向属性的key，我们可以再做一个DLL+Map，也可以存一个collection(List, Map)
easy case
不需要任何的顺序， set/list
// Some code
class Node{
Node prev;
Node next;
// Collection of keys share the same row field
Set<String> allStringShareSameFreq;
}hard case
同样的频率的情况下，对另一个field再进行比较和存储，再观察是不是变量为1的顺序模型again，如果是的话，可以再来一个map2+ dll2,而dll2 inside of dll1
// Some code
class Node{
Node prev;
Node next;
// Store another DLL2
AnotherOrderNode head;
AnotherOrderNode tail
// TreeMap, TreeSet
}case even more
无限套娃
Middle Level：所有API走流程
inc(String key)
case 1: 这个key是第一次出现
case1.1 看看有没有对应的freq =1 的node
创建一个并且加入map +dll(set)
case1.2 如果已经存在在freq为1的弄的
把这个新的data加入到已经存在的node set里面
case 2: 这个key不是第一次出现
首先得知道他是第几次出现（map里面拿freq node）
我们应该把这个node放到现在的freq+1的freq node
这个freq + 1一定是你现在的freqNode.next么？
case2.1 不存在freq +1 的node
创建一个freq + 1的freqNode并且把这个node插入到当前freqNode之后
对应的key加入到这个你插入的freqNode里
case2.2 存在freq + 1的node
对应的key加入到这个你插入的freqNode里
不管存在不存在，现在key都不是freqNode里的人了，你得从freqNode里把这个key删除
你现在把这个key当前的freqNode里删除之后，有没有可能当前的freqNode里就没有任何key了？
如果空了，我们就要连着这个FreqNode + Map删除
dec(String key)
case 1: 这个key是第一次出现
直接return
case 2: 这个key不是第一次出现
首先得知道他是第几次出现（map里面拿freq node）
我们应该把这个node放到现在的freq+1的freq node
这个key只出现了一次？我们不存在freq为0的FreqNode
删除这个key + check freq为1的FreqNode是否需要删除
这个freq - 1一定是你现在的freqNode.prev么？
case2.1 不存在freq - 1 的node
创建一个freq - 1的freqNode并且把这个node插入到当前freqNode之前
对应的key加入到这个你插入的freqNode里
case2.2 存在freq - 1的node
对应的key加入到这个你插入的freqNode里
不管存在不存在，现在key都不是freqNode里的人了，你得从freqNode里把这个key删除
你现在把这个key当前的freqNode里删除之后，有没有可能当前的freqNode里就没有任何key了？
如果空了，我们就要连着这个FreqNode + Map删除
getMaxKey()
从tailNode里随便拿一个
getMinKey()
从headNode里随便拿一个
// Some code
public class AllOne {
MAp<String, FreqNode> map;
FreqNopde head;
FreqNode tail;
public AllOne() {
this.map = new HashMap<>();
this.head = this.tail = new FreqNode(-1);
head.next = tail;
tail.prev = head;
//如果不允许用dummy Node implement: this.head = this.tail = null;
}
public void inc(String key) {
FreqNode = temp = map.get(key);
if (temp == null) {
FreqNode firstNode = this.head.next;
if (firstNode.freq == 1) {
firstNode.values.add(key);
map.put(key, firstNode);
}else {
FreqNode newNode = insertNode(head, 1);
newNode.values.add(key);
map.put(key, firstNode);
}
} else {
FreqNode next = temp.next;
if (next.freq! = temp.freq + 1) {
next = insertNode(temp, temp.freq + 1);
}
next.values.add(key);
temp.values.remove(key);
map.put(key, next);
if (temp.values.size() == ) {
deleteNode(temp);
}
}
}
public void dec(String key) {
FreqNode temp = map.get(key);
if (temp == null) {
return;
} else {
if (temp.freq == 1) {
temp.values.remove(key);
if (temp.values.size() == 0) {
deleteNode(temp);
}
map.remove(key);
return;
}
FreqNode previous = temp.prev;
if (previous.freq != temp.freq - 1) {
previous = insertNode(previous, temp.freq - 1);
}
temp.values.remove(key);
previous.values.add(key);
map.put(key, previous);
if (temp.values.size() == 0) {
deleteNode(temp);
}
}
}
public String getMapKey() {
if (head.next == tail) {
return "";
}
FreqNode maxNode = tail.prev;
return maxNode.values.iterator().next();
}
public String getMinKey() {
if (head.next == tail) {
return "";
}
FreqNode minNode = head.next;
return minNode. values.iterator().next();
}
class FreqNode {
int freq;
Set<String> values; //二级结构里同享一个freq的所有string们
FreqNode next;
FreqNode prev;
public FreqNode(int freq) {
this.freq = freq;
this.values = new HashSet<>();
this.next = this.prev = null;
}
}
private FreqNode insertNode(FreqNode current, int freq) {
FreqNode newNode = new FreqNode(freq);
FreqNode next = current.next;
current.next = newNode;
newNode.next = next;
next.prev = newNode;
newNode.prev = current;
return newNode;
}
private void deleteNode(FreqNode current) {
FreqNode next = current.next;
FreqNode prev = current.prev;
prev.next = next;
next.prev = prev;
current.next = null;
current.prev = null;
}
}Last updated