长沙手机网站设计,php值班系统 wordpress,桂林漓江游船票价格,专做正品的护肤品网站文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接#xff1a;2671. 频率跟踪器
2. 题目解析
挺有意思的哈希表题目#xff0c;单独一个哈希表的话#xff0c;每次遍历去判断有没有数字出现的次数#xff0c;就会超时。 所以#xff0c;考虑两个哈希表的使用#xff… 文章目录 1. 题目来源2. 题目解析 1. 题目来源
链接2671. 频率跟踪器
2. 题目解析
挺有意思的哈希表题目单独一个哈希表的话每次遍历去判断有没有数字出现的次数就会超时。 所以考虑两个哈希表的使用一个哈希表来存储当前元素的次数是多少另一个哈希表存储次数出现的次数比较绕口…
当新数字进来
旧数字的次数出现的次数就要减1新数字的次数就需要加1
当有数字出去
旧数字的次数需要减少新数字的次数在减少的基础上再减少1
有点绕可以理解一下。 时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1) class FrequencyTracker {unordered_mapint, int cnt; // number 的出现次数unordered_mapint, 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}
};
