LeetCode 432. 全 O(1) 的数据结构
题目描述
题意分析
维护每个字符串的计数，支持加一、减一，以及返回任意计数最大或最小的字符串。新键从
1开始，计数减到0时删除；没有键时，查询返回空字符串。题目保证调用dec的键已经存在。每种操作都要求平均
O(1)。哈希表能快速找到某个键，却不能直接找到最小、最大计数；还需要利用每次计数只变化1的特点维护顺序。
解法：双向链表 + 哈希表
核心思路
[!blue]
将计数相同的键放入一个桶，非空桶按计数严格递增连接成双向链表，
nodes记录每个键所在的桶。始终保持三个条件：每个键恰好属于一个桶，定位表与桶内成员一致，链表中没有空桶。这样head.next就是最小计数桶，tail.prev就是最大计数桶。已有键从计数
c增到c+1时，目标桶若存在，一定是当前桶的后继，因为两个整数之间不可能还有其他计数。若后继计数不是c+1，就在当前桶后创建新桶。减到c-1同理，只需查看前驱；计数为1时则直接删除键。桶之间允许有计数空档，但每次操作都只需检查一个邻居，不需要遍历链表。迁移时，先把键放入目标桶并更新定位，再从旧桶移除；旧桶变空就摘除。新键总是进入最前面的计数
1桶，必要时新建。每次更新只影响相邻位置，因此迁移完成后，桶的有序性与上述三个条件继续成立，首尾查询始终正确。桶内还必须支持直接取一个成员和按键删除。Java 使用
LinkedHashSet，可直接取得链式迭代首项；Go 使用成员链表和key → 链表节点的映射，通过节点句柄删除，避免扫描成员。成员先后顺序没有题意要求，只用于实现这些常数时间操作。
解题步骤
- 新键进入计数一的桶，必要时在最前面创建。
- 已有键加一向后、减一向前，复用或创建目标桶。
- 计数从一减到零时，同时删除键与定位。
- 清理空桶，查询直接取对应端点桶的一个键。
首尾哨兵不存真实键。链表为空时两者直接相连；删掉最后一个键后，其空桶也会被摘除，因此空结构查询可由哨兵关系直接判断。
代码实现
// key -> bucket 的哈希表用于 O(1) 找到 key 所在桶。
class AllOne {
private final Bucket head;
private final Bucket tail;
private final Map<String, Bucket> nodes;
public AllOne() {
head = new Bucket(0);
tail = new Bucket(0);
head.next = tail;
tail.prev = head;
nodes = new HashMap<>();
}
public void inc(String key) {
if (!nodes.containsKey(key)) {
Bucket first = head.next;
if (first != tail && first.count == 1) {
first.keys.add(key);
nodes.put(key, first);
} else {
Bucket bucket = new Bucket(1);
bucket.keys.add(key);
insertAfter(head, bucket);
nodes.put(key, bucket);
}
return;
}
Bucket cur = nodes.get(key);
Bucket next = cur.next;
// 目标计数只差一，已有目标桶必在相邻位置
int nextCount = cur.count + 1;
if (next != tail && next.count == nextCount) {
next.keys.add(key);
nodes.put(key, next);
} else {
Bucket bucket = new Bucket(nextCount);
bucket.keys.add(key);
insertAfter(cur, bucket);
nodes.put(key, bucket);
}
// 移除旧桶成员，成员为空时摘掉旧桶
cur.keys.remove(key);
if (cur.keys.isEmpty()) {
remove(cur);
}
}
public void dec(String key) {
Bucket cur = nodes.get(key);
if (cur == null) {
return;
}
if (cur.count == 1) {
// 移除旧桶成员，成员为空时摘掉旧桶
cur.keys.remove(key);
nodes.remove(key);
if (cur.keys.isEmpty()) {
remove(cur);
}
return;
}
Bucket prev = cur.prev;
// 减一后的目标桶若不存在，就插在当前桶前方
int prevCount = cur.count - 1;
if (prev != head && prev.count == prevCount) {
prev.keys.add(key);
nodes.put(key, prev);
} else {
Bucket bucket = new Bucket(prevCount);
bucket.keys.add(key);
insertAfter(prev, bucket);
nodes.put(key, bucket);
}
// 移除旧桶成员，成员为空时摘掉旧桶
cur.keys.remove(key);
if (cur.keys.isEmpty()) {
remove(cur);
}
}
public String getMaxKey() {
if (tail.prev == head) {
return "";
}
return tail.prev.keys.iterator().next();
}
public String getMinKey() {
if (head.next == tail) {
return "";
}
return head.next.keys.iterator().next();
}
private void insertAfter(Bucket node, Bucket add) {
add.prev = node;
add.next = node.next;
node.next.prev = add;
node.next = add;
}
private void remove(Bucket node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private static class Bucket {
int count;
Set<String> keys = new LinkedHashSet<>();
Bucket prev;
Bucket next;
Bucket(int count) {
this.count = count;
}
}
}
import "container/list"
// key -> bucket 的哈希表用于 O(1) 找到 key 所在桶。
type Bucket struct {
count int
keys *list.List
members map[string]*list.Element
prev *Bucket
next *Bucket
}
func newBucket(count int) *Bucket {
return &Bucket{count: count, keys: list.New(), members: make(map[string]*list.Element)}
}
func (b *Bucket) addKey(key string) {
// 保存成员节点句柄，删除时不需要扫描链表。
b.members[key] = b.keys.PushBack(key)
}
func (b *Bucket) removeKey(key string) {
// 成员链表与句柄表同步移除，保持一一对应。
b.keys.Remove(b.members[key])
delete(b.members, key)
}
type AllOne struct {
head *Bucket
tail *Bucket
nodes map[string]*Bucket
}
func Constructor() AllOne {
head := newBucket(0)
tail := newBucket(0)
head.next = tail
tail.prev = head
return AllOne{head: head, tail: tail, nodes: make(map[string]*Bucket)}
}
func (a *AllOne) Inc(key string) {
if _, ok := a.nodes[key]; !ok {
first := a.head.next
if first != a.tail && first.count == 1 {
first.addKey(key)
a.nodes[key] = first
} else {
bucket := newBucket(1)
bucket.addKey(key)
a.insertAfter(a.head, bucket)
a.nodes[key] = bucket
}
return
}
cur := a.nodes[key]
next := cur.next
// 目标计数只差一，已有目标桶必在相邻位置
nextCount := cur.count + 1
if next != a.tail && next.count == nextCount {
next.addKey(key)
a.nodes[key] = next
} else {
bucket := newBucket(nextCount)
bucket.addKey(key)
a.insertAfter(cur, bucket)
a.nodes[key] = bucket
}
// 移除旧桶成员，成员为空时摘掉旧桶
cur.removeKey(key)
if cur.keys.Len() == 0 {
a.remove(cur)
}
}
func (a *AllOne) Dec(key string) {
cur, ok := a.nodes[key]
if !ok {
return
}
if cur.count == 1 {
// 移除旧桶成员，成员为空时摘掉旧桶
cur.removeKey(key)
delete(a.nodes, key)
if cur.keys.Len() == 0 {
a.remove(cur)
}
return
}
prev := cur.prev
// 减一后的目标桶若不存在，就插在当前桶前方
prevCount := cur.count - 1
if prev != a.head && prev.count == prevCount {
prev.addKey(key)
a.nodes[key] = prev
} else {
bucket := newBucket(prevCount)
bucket.addKey(key)
a.insertAfter(prev, bucket)
a.nodes[key] = bucket
}
// 移除旧桶成员，成员为空时摘掉旧桶
cur.removeKey(key)
if cur.keys.Len() == 0 {
a.remove(cur)
}
}
func (a *AllOne) GetMaxKey() string {
if a.tail.prev == a.head {
return ""
}
return a.tail.prev.keys.Front().Value.(string)
}
func (a *AllOne) GetMinKey() string {
if a.head.next == a.tail {
return ""
}
return a.head.next.keys.Front().Value.(string)
}
func (a *AllOne) insertAfter(node *Bucket, add *Bucket) {
add.prev = node
add.next = node.next
node.next.prev = add
node.next = add
}
func (a *AllOne) remove(node *Bucket) {
node.prev.next = node.next
node.next.prev = node.prev
}
复杂度分析
- 时间复杂度：四种操作平均均摊 $O(1)$。题目限制键长度，哈希操作平均为常数时间；每次只迁移一个键、修改相邻桶，查询直接取端点桶的成员。
- 空间复杂度：逻辑存储为 $O(K)$，其中
K为当前键数。每个真实桶至少含一个键，因此桶数也不超过K；容器实际分配容量还受历史峰值影响。
关键点总结
[!green]
- 常数时间来自“计数只改变一”，目标桶只可能位于相邻位置。
- 每个键的桶定位、桶内成员以及桶链表必须同步更新。
- 非空且有序的桶链表，让极值查询等价于读取首尾。
易错点总结
[!yellow]
- 旧桶变空却保留，会让端点查询取不到键。
- 迁移后不更新定位，下次修改会从旧桶出发。
- 计数归零后保留键，会让已删除项继续参与最小值查询。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 460. LFU 缓存 | 困难 | 同样用频次桶和哈希定位元素，原题还按频率与使用先后淘汰，本题直接查询最小/最大频次键。 |
| 895. 最大频率栈 | 困难 | 同样按出现频率组织元素，原题只需要最高频并按最近使用打破平局，本题支持任意键增减及双端极值查询。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！