LeetCode 432. 全 O(1) 的数据结构

Categories:

题目描述
思路分析
1. 解法一：双向链表 + 哈希表（推荐）
相似题目

题目描述

✅ 432. 全 O(1) 的数据结构

思路分析

解法一：双向链表 + 哈希表（推荐）

核心思路：

双向链表维护计数桶，桶内保存拥有相同计数的 key 集合。

key -> bucket 的哈希表用于 O(1) 找到 key 所在桶。

inc/dec 时移动 key 到相邻计数桶，空桶及时删除，getMax/Min 直接取链表首尾。

复杂度分析：

时间复杂度：O(1) 均摊，每个操作常数时间。

空间复杂度：O(n)，其中 n 表示不同 key 的数量。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

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 HashSet<>();
        Bucket prev;
        Bucket next;

        Bucket(int count) {
            this.count = count;
        }
    }
}

type Bucket struct {
	count int
	keys  map[string]struct{}
	prev  *Bucket
	next  *Bucket
}

type AllOne struct {
	head  *Bucket
	tail  *Bucket
	nodes map[string]*Bucket
}

func Constructor() AllOne {
	head := &Bucket{count: 0, keys: map[string]struct{}{}}
	tail := &Bucket{count: 0, keys: map[string]struct{}{}}
	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.keys[key] = struct{}{}
			a.nodes[key] = first
		} else {
			bucket := &Bucket{count: 1, keys: map[string]struct{}{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.keys[key] = struct{}{}
		a.nodes[key] = next
	} else {
		bucket := &Bucket{count: nextCount, keys: map[string]struct{}{key: {}}}
		a.insertAfter(cur, bucket)
		a.nodes[key] = bucket
	}

	delete(cur.keys, key)
	if len(cur.keys) == 0 {
		a.remove(cur)
	}
}

func (a *AllOne) Dec(key string) {
	cur, ok := a.nodes[key]
	if !ok {
		return
	}

	if cur.count == 1 {
		delete(cur.keys, key)
		delete(a.nodes, key)
		if len(cur.keys) == 0 {
			a.remove(cur)
		}
		return
	}

	prev := cur.prev
	prevCount := cur.count - 1

	if prev != a.head && prev.count == prevCount {
		prev.keys[key] = struct{}{}
		a.nodes[key] = prev
	} else {
		bucket := &Bucket{count: prevCount, keys: map[string]struct{}{key: {}}}
		a.insertAfter(prev, bucket)
		a.nodes[key] = bucket
	}

	delete(cur.keys, key)
	if len(cur.keys) == 0 {
		a.remove(cur)
	}
}

func (a *AllOne) GetMaxKey() string {
	if a.tail.prev == a.head {
		return ""
	}
	for k := range a.tail.prev.keys {
		return k
	}
	return ""
}

func (a *AllOne) GetMinKey() string {
	if a.head.next == a.tail {
		return ""
	}
	for k := range a.head.next.keys {
		return k
	}
	return ""
}

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
}

相似题目

题目	难度	考察点
355. 设计推特	中等	数据结构设计
146. LRU 缓存	中等	哈希表 + 链表
460. LFU 缓存	困难	计数桶
380. O(1) 时间插入、删除和获取随机元素	中等	哈希表
981. 基于时间的键值存储	中等	哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/41930761