本题实质考察了 LFU 的实现方式。
原题链接如下：
432. 全 O(1) 的数据结构
必和常见的优先队列构建 LFU 的方法不同，须以 O(1) 的时间复杂度完成查找最值和增删新值的操作。
数据的具体操作如下：
1
2
3
4
5
6
7
8
| AllOne allOne = new AllOne();
allOne.inc("hello");
allOne.inc("hello");
allOne.getMaxKey();
allOne.getMinKey();
allOne.inc("leet");
allOne.getMaxKey();
allOne.getMinKey();
|
对应的 4 个获取最值的操作会得到 4 个输出数据，分别是：
1
2
3
4
| hello
hello
hello
leet
|
如果只是要保证插入、获取的实践复杂度为 O(1) 的话，不难想到可以使用链表结构存储数据，同时不必在每次要获取最值的时候进行遍历或者排序。但是需要注意的是：
- 链表结点存储计数值和同计数的所有字符串
- 每次插入和删除保证结点按照计数的大小有序排列
然后，自然需要解决随机访问链表结点的问题，自然需要引入哈希表存储链表的值和结点地址。当然本题中的链表实际可能存储了很多的字符串，这每一个字符串都和链表的地址构成一个键值对。
本题的难点在于代码实现中，需要注意：
- 对与已有字符串的计数修改会改变字符串在链表中的位置，甚至进而引发链表的结构更改
- 增加计数会导致原计数的结点中移除这个字符串，不止有增加结点的可能
- 减少计数可能导致字符串加入新的计数结点，甚至新建结点，不止要考虑删除结点的可能
- 为了保证快速访问，必须清理不再保存字符串的结点
- 为了快速访问最大值和最小值（即链表的两端），应该使用双向链表，并且加入哨兵结点
- 为了方便删除操作，应当使用循环链表（亦称环形链表）
注意
在处理循环双向链表的删除最后一个结点和新增第一个结点的时候极易发生 NPE，需要特别注意指针的处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| class AllOne() {
private val head = Node("", 0)
private val map = mutableMapOf<String, Node>()
fun inc(key: String) {
if (key in map.keys) {
val curr = map[key]!!
val next = curr.next
if (next == head || next.count > curr.count + 1) {
val node = Node(key, curr.count + 1)
map[key] = node
curr.insertNext(node)
} else {
next.keys.add(key)
map[key] = next
}
curr.keys.remove(key)
if (curr.keys.isEmpty()) curr.delete()
} else if (head.next == head || head.next.count > 1) {
val node = Node(key, 1)
map[key] = node
head.insertNext(node)
} else {
head.next.keys.add(key)
map[key] = head.next
}
}
fun dec(key: String) {
val curr = map[key]!!
val prev = curr.prev
if (curr.count == 1) map.remove(key)
else if (prev == head || prev.count < curr.count - 1) {
val node = Node(key, curr.count - 1)
map[key] = node
prev.insertNext(node)
} else {
prev.keys.add(key)
map[key] = prev
}
curr.keys.remove(key)
if (curr.keys.isEmpty()) curr.delete()
}
fun getMaxKey(): String {
return head.prev.keys.first()
}
fun getMinKey(): String {
return head.next.keys.first()
}
companion object {
class Node(key: String, var count: Int) {
var prev = this
var next = this
val keys = mutableSetOf<String>()
init {
keys.add(key)
}
fun insertNext(node: Node) {
node.prev = this
node.next = this.next
this.next = node
node.next.prev = node
}
fun delete() {
this.prev.next = this.next
this.next.prev = this.prev
}
}
}
}
|