题目
请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 AllOne 类：
AllOne() 初始化数据结构的对象。
inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 “” 。
getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 “” 。
注意：每个函数都应当满足 O(1) 平均时间复杂度。
示例：
输入
[“AllOne”, “inc”, “inc”, “getMaxKey”, “getMinKey”, “inc”, “getMaxKey”, “getMinKey”]
[[], [“hello”], [“hello”], [], [], [“leet”], [], []]
输出
[null, null, null, “hello”, “hello”, null, “hello”, “leet”]
解释
AllOne allOne = new AllOne();
allOne.inc(“hello”);
allOne.inc(“hello”);
allOne.getMaxKey(); // 返回 “hello”
allOne.getMinKey(); // 返回 “hello”
allOne.inc(“leet”);
allOne.getMaxKey(); // 返回 “hello”
allOne.getMinKey(); // 返回 “leet”
参数范围：
1 <= key.length <= 10
key 由小写英文字母组成
测试用例保证：在每次调用 dec 时，数据结构中总存在 key
最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 104 次
2023年5月版
class AllOne { public: AllOne() { } void inc(string key) { int iPreNum = m_mStrNums[key]; m_mStrNums[key]++; if (iPreNum > 0) { auto it = m_mNumStrs[iPreNum].find(key); m_mNumStrs[iPreNum].erase(it); if (m_mNumStrs[iPreNum].empty()) { m_mNumStrs.erase(iPreNum); } } m_mNumStrs[iPreNum + 1].emplace(key); } void dec(string key) { int iPreNum = m_mStrNums[key]; m_mStrNums[key]–; auto it = m_mNumStrs[iPreNum].find(key); m_mNumStrs[iPreNum].erase(it); if (m_mNumStrs[iPreNum].empty()) { m_mNumStrs.erase(iPreNum); } if (iPreNum > 1) { m_mNumStrs[iPreNum - 1].emplace(key); } } string getMaxKey() { if (m_mNumStrs.empty()) { return “”; } return *m_mNumStrs.rbegin()->second.begin(); } string getMinKey() { if (m_mNumStrs.empty()) { return “”; } return *m_mNumStrs.begin()->second.begin(); } std::unordered_map<string, int> m_mStrNums; std::map<int ,std::unordered_multiset> m_mNumStrs; };
2023年8月版
class AllOne { public: AllOne() { } void inc(string key) { if (m_mStrNum.count(key)) { auto it = m_mStrNum[key]; const int iNewNum = it->first + 1; auto ij = it; ++ij; it->second.erase(key); if (0 == it->second.size()) { m_list.erase(it); } bool bNeedAdd = true; if (m_list.end() != ij ) { bNeedAdd = iNewNum != ij->first; } if (bNeedAdd) { ij = m_list.emplace(ij, iNewNum, std::set{key}); } else { ij->second.emplace(key); } m_mStrNum[key] = ij; } else { bool bNeedAdd = true; auto it = m_list.begin(); if (it != m_list.end()) { bNeedAdd = 1 != it->first; } if (bNeedAdd) { it = m_list.emplace(m_list.begin(), 1, std::set{key}); } else { it->second.emplace(key); } m_mStrNum[key] = m_list.begin(); } } void dec(string key) { auto it = m_mStrNum[key]; const int iNewNum = it->first - 1; if (m_list.begin() != it) { auto ij = it; –ij; if (ij->first == iNewNum) { it->second.erase(key); if (0 == it->second.size()) { m_list.erase(it); } ij->second.emplace(key); if (0 == iNewNum) { m_mStrNum.erase(key); } else { m_mStrNum[key] = ij; } return; } } if (0 == iNewNum) { m_mStrNum.erase(key); } else { it = m_list.emplace(it, iNewNum, set{key}); m_mStrNum[key] = it; ++it; } it->second.erase(key); if (0 == it->second.size()) { it = m_list.erase(it); } } string getMaxKey() { if (m_list.rbegin() == m_list.rend()) { return “”; } return *m_list.rbegin()->second.begin(); } string getMinKey() { if (m_list.begin() == m_list.end()) { return “”; } return *m_list.begin()->second.begin(); } typedef std::list < std::pair<int, std::set>> LIST; std::unordered_map<string, LIST::iterator> m_mStrNum; LIST m_list; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
