M哈希表

文章结构概览

• • 1. 选题依据
    • 2. 题目释义

1. 题目来源

链接：2671. 频率跟踪器

题目解析与研究框架

这道关于哈希表的题目颇具趣味性，如果仅使用一个哈希表，在每次遍历时判断某个数字出现的次数，会导致超时问题。因此，需要引入两个哈希表，其中一个用于记录当前元素出现的次数，另一个则用于统计次数出现的频率，这种结构略显复杂。

当有新的数字进入时：

• 原本存在的数字对应的次数需要减少1，同时新数字的出现次数则要增加1。

当有数字被移除时：

• 原有数字的出现次数应相应减少，而新数字在该基础上还需进一步减少1。

整体逻辑较为复杂，建议仔细理解。

• 时间复杂度 ：O(n)
• 空间复杂度 ：O(1)

    class FrequencyTracker {
    unordered_map<int, int> cnt; // number 的出现次数
    unordered_map<int, int> freq; // number 的出现次数的出现次数
    public:
    Fre