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

困难设计力扣原题 ↗

在线写代码并运行看动画推演问 AI 讲解

题目描述

设计一个类 AllOne，用来记录每个字符串出现的次数，并能随时取出次数最多和最少的字符串。

AllOne()：创建一个空的结构。inc(key)：把 key 的次数加 1；若 key 还没有记录，就以次数 1 加入。无返回值。

dec(key)：把 key 的次数减 1；减到 0 时将它移除。调用时 key 一定已经存在。无返回值。

getMaxKey()：返回任一次数最多的字符串；getMinKey()：返回任一次数最少的字符串。结构为空时这两个方法都返回空串 ""。

每个方法的平均时间复杂度都要求为 O(1)。

示例 1

输入：操作 = ["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"]
参数 = [[],["hello"],["hello"],[],[],["leet"],[],[]]
输出：[null,null,null,"hello","hello",null,"hello","leet"]

解释："hello" 加两次后最大最小都是它；再加入 "leet"（次数 1），最大仍为 "hello"，最小变为 "leet"。

数据范围

1 <= key.length <= 10
key 只含小写英文字母。
每次调用 dec 时，key 都已在结构中。
四个方法合计调用不超过 5 * 10^4 次。

解题思路

把计数相同的键放进同一个“桶”，桶按计数从小到大串成一条带头尾哨兵的双向链表，再用哈希表 where 记录每个键所在的桶。inc 时键只会移到紧邻的下一个桶（计数 +1），不存在就在当前桶后面新建一个；dec 对称地移到前一个桶。旧桶空了就从链表中摘掉。这样链表始终有序，最大键在 tail.prev 桶里，最小键在 head.next 桶里。

为什么正确

链表中的桶计数严格递增且都非空；每个键恰好在计数等于自己计数的桶中。

复杂度分析

四个操作均为 O(1)；空间 O(不同键的个数)。

易错点

新桶必须插在旧桶的紧邻位置才能保持有序；要先把键放入新桶再删旧桶，否则旧桶被摘掉后就找不到插入位置；dec 到 0 时键要从 where 中删除，而不是放进计数 0 的桶。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Bucket:
    def __init__(self, cnt: int = 0):
        self.cnt = cnt
        self.keys = {}
        self.prev = None
        self.next = None

class AllOne:
    def __init__(self):
        self.head = Bucket()
        self.tail = Bucket()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.where = {}

    def _insert_after(self, node: Bucket, cnt: int) -> Bucket:
        b = Bucket(cnt)
        b.prev = node
        b.next = node.next
        node.next.prev = b
        node.next = b
        return b

    def _remove(self, node: Bucket) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def inc(self, key: str) -> None:
        cur = self.where.get(key, self.head)
        nxt = cur.next
        if nxt is self.tail or nxt.cnt != cur.cnt + 1:
            nxt = self._insert_after(cur, cur.cnt + 1)
        nxt.keys[key] = None
        self.where[key] = nxt
        if cur is not self.head:
            del cur.keys[key]
            if not cur.keys:
                self._remove(cur)

    def dec(self, key: str) -> None:
        cur = self.where[key]
        del cur.keys[key]
        if cur.cnt == 1:
            del self.where[key]
        else:
            prv = cur.prev
            if prv is self.head or prv.cnt != cur.cnt - 1:
                prv = self._insert_after(prv, cur.cnt - 1)
            prv.keys[key] = None
            self.where[key] = prv
        if not cur.keys:
            self._remove(cur)

    def getMaxKey(self) -> str:
        if self.tail.prev is self.head:
            return ""
        return next(iter(self.tail.prev.keys))

    def getMinKey(self) -> str:
        if self.head.next is self.tail:
            return ""
        return next(iter(self.head.next.keys))

class AllOne {
    private static class Bucket {
        int cnt;
        Set<String> keys = new LinkedHashSet<>();
        Bucket prev, next;
        Bucket(int c) {
            cnt = c;
        }
    }

    private Bucket head, tail;
    private Map<String, Bucket> where;

    public AllOne() {
        head = new Bucket(0);
        tail = new Bucket(0);
        head.next = tail;
        tail.prev = head;
        where = new HashMap<>();
    }

    private Bucket insertAfter(Bucket node, int cnt) {
        Bucket b = new Bucket(cnt);
        b.prev = node;
        b.next = node.next;
        node.next.prev = b;
        node.next = b;
        return b;
    }

    private void removeNode(Bucket node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void inc(String key) {
        Bucket cur = where.getOrDefault(key, head);
        Bucket nxt = cur.next;
        if (nxt == tail || nxt.cnt != cur.cnt + 1) {
            nxt = insertAfter(cur, cur.cnt + 1);
        }
        nxt.keys.add(key);
        where.put(key, nxt);
        if (cur != head) {
            cur.keys.remove(key);
            if (cur.keys.isEmpty()) {
                removeNode(cur);
            }
        }
    }

    public void dec(String key) {
        Bucket cur = where.get(key);
        cur.keys.remove(key);
        if (cur.cnt == 1) {
            where.remove(key);
        } else {
            Bucket prv = cur.prev;
            if (prv == head || prv.cnt != cur.cnt - 1) {
                prv = insertAfter(prv, cur.cnt - 1);
            }
            prv.keys.add(key);
            where.put(key, prv);
        }
        if (cur.keys.isEmpty()) {
            removeNode(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();
    }
}

struct Bucket {
    int cnt;
    unordered_set<string> keys;
    Bucket* prev;
    Bucket* next;
    Bucket(int c = 0) : cnt(c), prev(nullptr), next(nullptr) {}
};

class AllOne {
public:
    Bucket* head;
    Bucket* tail;
    unordered_map<string, Bucket*> where;

    AllOne() {
        head = new Bucket();
        tail = new Bucket();
        head->next = tail;
        tail->prev = head;
        where.clear();
    }

    Bucket* insertAfter(Bucket* node, int cnt) {
        Bucket* b = new Bucket(cnt);
        b->prev = node;
        b->next = node->next;
        node->next->prev = b;
        node->next = b;
        return b;
    }

    void removeNode(Bucket* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void inc(string key) {
        Bucket* cur = where.count(key) ? where[key] : head;
        Bucket* nxt = cur->next;
        if (nxt == tail || nxt->cnt != cur->cnt + 1) {
            nxt = insertAfter(cur, cur->cnt + 1);
        }
        nxt->keys.insert(key);
        where[key] = nxt;
        if (cur != head) {
            cur->keys.erase(key);
            if (cur->keys.empty()) {
                removeNode(cur);
            }
        }
    }

    void dec(string key) {
        Bucket* cur = where[key];
        cur->keys.erase(key);
        if (cur->cnt == 1) {
            where.erase(key);
        } else {
            Bucket* prv = cur->prev;
            if (prv == head || prv->cnt != cur->cnt - 1) {
                prv = insertAfter(prv, cur->cnt - 1);
            }
            prv->keys.insert(key);
            where[key] = prv;
        }
        if (cur->keys.empty()) {
            removeNode(cur);
        }
    }

    string getMaxKey() {
        if (tail->prev == head) {
            return "";
        }
        return *tail->prev->keys.begin();
    }

    string getMinKey() {
        if (head->next == tail) {
            return "";
        }
        return *head->next->keys.begin();
    }
};

type Bucket struct {
	cnt        int
	keys       map[string]bool
	prev, next *Bucket
}

func newBucket(cnt int) *Bucket {
	return &Bucket{cnt: cnt, keys: map[string]bool{}}
}

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

func Constructor() AllOne {
	head := newBucket(0)
	tail := newBucket(0)
	head.next = tail
	tail.prev = head
	return AllOne{head: head, tail: tail, where: map[string]*Bucket{}}
}

func (this *AllOne) insertAfter(node *Bucket, cnt int) *Bucket {
	b := newBucket(cnt)
	b.prev = node
	b.next = node.next
	node.next.prev = b
	node.next = b
	return b
}

func (this *AllOne) removeNode(node *Bucket) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *AllOne) Inc(key string) {
	cur, ok := this.where[key]
	if !ok {
		cur = this.head
	}
	nxt := cur.next
	if nxt == this.tail || nxt.cnt != cur.cnt+1 {
		nxt = this.insertAfter(cur, cur.cnt+1)
	}
	nxt.keys[key] = true
	this.where[key] = nxt
	if cur != this.head {
		delete(cur.keys, key)
		if len(cur.keys) == 0 {
			this.removeNode(cur)
		}
	}
}

func (this *AllOne) Dec(key string) {
	cur := this.where[key]
	delete(cur.keys, key)
	if cur.cnt == 1 {
		delete(this.where, key)
	} else {
		prv := cur.prev
		if prv == this.head || prv.cnt != cur.cnt-1 {
			prv = this.insertAfter(prv, cur.cnt-1)
		}
		prv.keys[key] = true
		this.where[key] = prv
	}
	if len(cur.keys) == 0 {
		this.removeNode(cur)
	}
}

func anyKey(m map[string]bool) string {
	for k := range m {
		return k
	}
	return ""
}

func (this *AllOne) GetMaxKey() string {
	if this.tail.prev == this.head {
		return ""
	}
	return anyKey(this.tail.prev.keys)
}

func (this *AllOne) GetMinKey() string {
	if this.head.next == this.tail {
		return ""
	}
	return anyKey(this.head.next.keys)
}

class Bucket {
    constructor(cnt = 0) {
        this.cnt = cnt;
        this.keys = new Set();
        this.prev = null;
        this.next = null;
    }
}

class AllOne {
    constructor() {
        this.head = new Bucket();
        this.tail = new Bucket();
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.where = new Map();
    }

    insertAfter(node, cnt) {
        const b = new Bucket(cnt);
        b.prev = node;
        b.next = node.next;
        node.next.prev = b;
        node.next = b;
        return b;
    }

    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    inc(key) {
        const cur = this.where.get(key) || this.head;
        let nxt = cur.next;
        if (nxt === this.tail || nxt.cnt !== cur.cnt + 1) {
            nxt = this.insertAfter(cur, cur.cnt + 1);
        }
        nxt.keys.add(key);
        this.where.set(key, nxt);
        if (cur !== this.head) {
            cur.keys.delete(key);
            if (cur.keys.size === 0) {
                this.removeNode(cur);
            }
        }
    }

    dec(key) {
        const cur = this.where.get(key);
        cur.keys.delete(key);
        if (cur.cnt === 1) {
            this.where.delete(key);
        } else {
            let prv = cur.prev;
            if (prv === this.head || prv.cnt !== cur.cnt - 1) {
                prv = this.insertAfter(prv, cur.cnt - 1);
            }
            prv.keys.add(key);
            this.where.set(key, prv);
        }
        if (cur.keys.size === 0) {
            this.removeNode(cur);
        }
    }

    getMaxKey() {
        if (this.tail.prev === this.head) {
            return "";
        }
        return this.tail.prev.keys.values().next().value;
    }

    getMinKey() {
        if (this.head.next === this.tail) {
            return "";
        }
        return this.head.next.keys.values().next().value;
    }
}

class Bucket {
    cnt: number;
    keys: Set<string>;
    prev: Bucket | null;
    next: Bucket | null;

    constructor(cnt: number = 0) {
        this.cnt = cnt;
        this.keys = new Set();
        this.prev = null;
        this.next = null;
    }
}

class AllOne {
    head: Bucket;
    tail: Bucket;
    where: Map<string, Bucket>;

    constructor() {
        this.head = new Bucket();
        this.tail = new Bucket();
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.where = new Map();
    }

    insertAfter(node: Bucket, cnt: number): Bucket {
        const b = new Bucket(cnt);
        b.prev = node;
        b.next = node.next;
        node.next!.prev = b;
        node.next = b;
        return b;
    }

    removeNode(node: Bucket): void {
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
    }

    inc(key: string): void {
        const cur = this.where.get(key) || this.head;
        let nxt = cur.next!;
        if (nxt === this.tail || nxt.cnt !== cur.cnt + 1) {
            nxt = this.insertAfter(cur, cur.cnt + 1);
        }
        nxt.keys.add(key);
        this.where.set(key, nxt);
        if (cur !== this.head) {
            cur.keys.delete(key);
            if (cur.keys.size === 0) {
                this.removeNode(cur);
            }
        }
    }

    dec(key: string): void {
        const cur = this.where.get(key)!;
        cur.keys.delete(key);
        if (cur.cnt === 1) {
            this.where.delete(key);
        } else {
            let prv = cur.prev!;
            if (prv === this.head || prv.cnt !== cur.cnt - 1) {
                prv = this.insertAfter(prv, cur.cnt - 1);
            }
            prv.keys.add(key);
            this.where.set(key, prv);
        }
        if (cur.keys.size === 0) {
            this.removeNode(cur);
        }
    }

    getMaxKey(): string {
        if (this.tail.prev === this.head) {
            return "";
        }
        return this.tail.prev!.keys.values().next().value as string;
    }

    getMinKey(): string {
        if (this.head.next === this.tail) {
            return "";
        }
        return this.head.next!.keys.values().next().value as string;
    }
}

载入编辑器，自己跑一遍 →

设计专题的其他题目

查看设计全部题目 →