[M哈希表] lc2671. 频率跟踪器(哈希表+思维)

本文主要是介绍[M哈希表] lc2671. 频率跟踪器(哈希表+思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目来源

链接：2671. 频率跟踪器

2. 题目解析

挺有意思的哈希表题目，单独一个哈希表的话，每次遍历去判断有没有数字出现的次数，就会超时。
所以，考虑两个哈希表的使用，一个哈希表来存储当前元素的次数是多少，另一个哈希表存储次数出现的次数，比较绕口…

当新数字进来：

• 旧数字的次数出现的次数就要减1，新数字的次数就需要加1

当有数字出去：

• 旧数字的次数需要减少，新数字的次数在减少的基础上再减少1

有点绕，可以理解一下。

---

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

---

class FrequencyTracker {unordered_map<int, int> cnt; // number 的出现次数unordered_map<int, int> freq; // number 的出现次数的出现次数
public:FrequencyTracker() {}void add(int number) {--freq[cnt[number]]; // 去掉一个旧的 cnt[number]++freq[++cnt[number]]; // 添加一个新的 cnt[number]}void deleteOne(int number) {if (!cnt[number]) return; // 不删除任何内容--freq[cnt[number]]; // 去掉一个旧的 cnt[number]++freq[--cnt[number]]; // 添加一个新的 cnt[number]}bool hasFrequency(int frequency) {return freq[frequency]; // 至少有一个 number 的出现次数恰好为 frequency}
};

这篇关于[M哈希表] lc2671. 频率跟踪器(哈希表+思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---