这是一个非常有意思的数据结构设计题，要求我们设计一个支持所有操作的时间复杂度都必须是 O(1)的数据结构。
代码逻辑
这道题的难点在于:
如何在 O(1) 时间内既能修改计数,又能快速找到最大/最小值?
如果只用 HashMap 存储计数,修改很快,但找最大/最小值需要遍历,时间复杂度是 O(n)。
如果用排序结构,查找最大/最小值很快,但插入删除的时间复杂度又无法保证 O(1)。
为了解决这个难题，我的思路是用一个双向链表按计数大小有序地存储所有"桶"(Bucket)，其中每个桶代表一个特定的计数值,包含所有该计数的 key，再用一个 HashMap 记录每个 key 当前所在的桶。
1. Bucket(桶)结构
1
2
3
4
5
6
7
8
9
10
11
12
|
class Bucket {
public HashSet<String> set; // 存储所有该计数的 key
public int cnt; // 计数值
public Bucket last; // 前驱节点
public Bucket next; // 后继节点
public Bucket(String s, int c) {
set = new HashSet<>();
set.add(s);
cnt = c;
}
}
|
2. inc(key) - 增加计数
如果key 不存在，需要创建计数为 1 的桶；如果 head.next 的计数正好是 1,直接加入该桶，否则,在 head 后创建新桶。
如果key 已存在，从当前桶移动到下一个计数的桶，如果 next 的计数正好是 cnt+1,直接加入，否则,创建新桶插入当前桶后面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
if (!map.containsKey(key)) {
if (head.next.cnt == 1) {
map.put(key, head.next);
head.next.set.add(key);
} else {
Bucket newBucket = new Bucket(key, 1);
map.put(key, newBucket);
insert(head, newBucket);
}
}else {
Bucket bucket = map.get(key);
if (bucket.next.cnt == bucket.cnt + 1) {
map.put(key, bucket.next);
bucket.next.set.add(key);
} else {
Bucket newBucket = new Bucket(key, bucket.cnt + 1);
map.put(key, newBucket);
insert(bucket, newBucket);
}
bucket.set.remove(key);
if (bucket.set.isEmpty()) {
remove(bucket); // 如果桶空了,删除该桶
}
}
|
3. dec(key) - 减少计数
如果计数减到 0,需要从 map 中删除该 key，否则,向前移动到计数减 1 的桶。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public void dec(String key) {
Bucket bucket = map.get(key);
if (bucket.cnt == 1) {
map.remove(key); // 计数为0,彻底删除
} else {
if (bucket.last.cnt == bucket.cnt - 1) {
map.put(key, bucket.last);
bucket.last.set.add(key);
} else {
Bucket newBucket = new Bucket(key, bucket.cnt - 1);
map.put(key, newBucket);
insert(bucket.last, newBucket);
}
}
bucket.set.remove(key);
if (bucket.set.isEmpty()) {
remove(bucket);
}
}
|
4. getMaxKey() 和 getMinKey()
1
2
3
4
5
6
7
|
public String getMaxKey() {
return tail.last.set.iterator().next();
}
public String getMinKey() {
return head.next.set.iterator().next();
}
|
5.insert() - 在指定位置插入桶
1
2
3
4
5
6
|
private void insert(Bucket cur, Bucket pos) {
cur.next.last = pos;
pos.next = cur.next;
cur.next = pos;
pos.last = cur;
}
|
6.remove() - 删除桶
1
2
3
4
|
private void remove(Bucket cur) {
cur.last.next = cur.next;
cur.next.last = cur.last;
}
|
完整代码
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
class AllOne {
class Bucket {
public HashSet<String> set;
public int cnt;
public Bucket last;
public Bucket next;
public Bucket(String s, int c) {
set = new HashSet<>();
set.add(s);
cnt = c;
}
}
private void insert(Bucket cur, Bucket pos) {
cur.next.last = pos;
pos.next = cur.next;
cur.next = pos;
pos.last = cur;
}
private void remove(Bucket cur) {
cur.last.next = cur.next;
cur.next.last = cur.last;
}
Bucket head; // 哨兵头节点(cnt=0)
Bucket tail; // 哨兵尾节点(cnt=MAX)
HashMap<String, Bucket> map; // key -> 所在桶的映射
public AllOne() {
head = new Bucket("",0);
tail = new Bucket("",Integer.MAX_VALUE);
head.next = tail;
tail.last = head;
map = new HashMap<>();
}
public void inc(String key){
if(!map.containsKey(key)){
if(head.next.cnt==1){
map.put(key,head.next);
head.next.set.add(key);
}else {
Bucket newBucket = new Bucket(key,1);
map.put(key,newBucket);
insert(head,newBucket);
}
}else{
Bucket bucket = map.get(key);
if(bucket.next.cnt==bucket.cnt+1){
map.put(key,bucket.next);
bucket.next.set.add(key);
}else{
Bucket newBucket = new Bucket(key, bucket.cnt+1);
map.put(key,newBucket);
insert(bucket,newBucket);
}
bucket.set.remove(key);
if(bucket.set.isEmpty()){
remove(bucket);// 如果桶空了,删除该桶
}
}
}
public void dec(String key){
Bucket bucket = map.get(key);
if(bucket.cnt==1){
map.remove(key);// 计数为0,彻底删除
}else{
if(bucket.last.cnt==bucket.cnt-1){
map.put(key,bucket.last);
bucket.last.set.add(key);
}else{
Bucket newBucket = new Bucket(key,bucket.cnt-1);
map.put(key,newBucket);
insert(bucket.last,newBucket);
}
}
bucket.set.remove(key);
if(bucket.set.isEmpty()){
remove(bucket);
}
}
public String getMaxKey(){
return tail.last.set.iterator().next();
}
public String getMinKey(){
return head.next.set.iterator().next();
}
}
|
如果觉得有帮助,欢迎点赞关注! 🌟