0432. All O`one Data Structure ============================== 题目信息 -------- :题号: 0432 :难度: Hard :主题: 设计、字符串计数、最小键、最大键 :原题: `LeetCode 0432 `_ :重点: ``inc``/``dec`` 修改跨调用计数、计数降到零时删除键、空结构返回空字符串、全部操作平均 ``O(1)`` 题目重述 -------- 实现 ``AllOne`` 数据结构,维护若干字符串键及其正整数计数。``inc(key)`` 将键的计数加 1;键不存在时先以计数 0 处理,因此调用后计数为 1。``dec(key)`` 将现有键的计数减 1;若计数变为 0,则从结构中删除该键,题目保证调用 ``dec`` 时键一定存在。 ``getMaxKey()`` 返回任意一个计数最大的键,``getMinKey()`` 返回任意一个计数最小的键;若结构为空,两者都返回空字符串 ``""``。并列时可以返回其中任意一个键。所有操作都要求平均时间复杂度为 ``O(1)``。 键只包含小写英文字母,长度位于 ``[1, 10]``;总调用次数不超过 ``5 * 10^4``。同一对象必须在连续调用之间保存全部计数状态。 自建示例 -------- 最大值和最小值来自不同键: .. code-block:: text 调用:inc("apple"), inc("pear"), inc("apple"), getMaxKey(), getMinKey() 查询输出:"apple"、"pear" 解释:apple 的计数为 2,pear 的计数为 1,因此最大键和最小键分别唯一确定。 计数降到零后删除: .. code-block:: text 调用:inc("x"), dec("x"), getMaxKey(), getMinKey() 查询输出:""、"" 解释:dec 后 x 的计数变为 0 并被删除,结构重新为空。 按计数维护相邻桶 ------------------ 用双向链表按计数从小到大排列桶,每个桶保存同一计数下的所有键;再用哈希表把每个键定位到所在桶。``inc`` 只需把键移动到计数加一的相邻桶,``dec`` 移动到计数减一的相邻桶;相邻桶不存在时在对应位置创建。桶空后立即删除,链表首尾就分别代表最小和最大计数。 链表迭代器和哈希映射共同保证移动、插入和删除都是平均常数时间;并列键从桶的集合中任取即可。 C++ 实现 -------- .. code-block:: cpp class AllOne { struct Bucket { int count; std::unordered_set keys; }; std::list buckets; std::unordered_map::iterator> where; public: void inc(std::string key) { auto it = where.find(key); if (it == where.end()) { if (buckets.empty() || buckets.front().count != 1) { buckets.push_front({1, {}}); } buckets.front().keys.insert(key); where[key] = buckets.begin(); return; } auto bucket = it->second; auto next = std::next(bucket); if (next == buckets.end() || next->count != bucket->count + 1) { next = buckets.insert(next, {bucket->count + 1, {}}); } next->keys.insert(key); where[key] = next; bucket->keys.erase(key); if (bucket->keys.empty()) buckets.erase(bucket); } void dec(std::string key) { auto bucket = where[key]; if (bucket->count == 1) { bucket->keys.erase(key); where.erase(key); if (bucket->keys.empty()) buckets.erase(bucket); return; } auto previous = bucket; if (bucket == buckets.begin() || std::prev(bucket)->count != bucket->count - 1) { previous = buckets.insert(bucket, {bucket->count - 1, {}}); } else { previous = std::prev(bucket); } previous->keys.insert(key); where[key] = previous; bucket->keys.erase(key); if (bucket->keys.empty()) buckets.erase(bucket); } std::string getMaxKey() { if (buckets.empty()) return ""; return *buckets.back().keys.begin(); } std::string getMinKey() { if (buckets.empty()) return ""; return *buckets.front().keys.begin(); } }; 代码分析 -------- 键的计数变化只跨越相邻桶,哈希表始终指向移动后的有效迭代器;空桶删除后仍保持链表按计数有序。``dec`` 的调用契约保证键存在,因此 ``where[key]`` 不会创建错误状态。所有操作平均 ``O(1)``,额外空间为 ``O(键数量)``。