wy的leetcode刷题记录_Day91
声明
本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2024-3-21
前言
目录
- wy的leetcode刷题记录_Day91
- 声明
- 前言
- 2671. 频率跟踪器
- 题目介绍
- 思路
- 代码
- 收获
2671. 频率跟踪器
今天的每日一题是：2671. 频率跟踪器
题目介绍
请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。
实现 FrequencyTracker 类：
- FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。
- void add(int number)：添加一个 number 到数据结构中。
- void deleteOne(int number)：从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。
- bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。
示例 1：
输入 [“FrequencyTracker”, “add”, “add”, “hasFrequency”] [[], [3], [3],[2]]
输出 [null, null, null, true]
解释 FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(3); // 数据结构现在包含 [3]
frequencyTracker.add(3); //数据结构现在包含 [3, 3]
frequencyTracker.hasFrequency(2); // 返回 true ，因为 3 出现2 次
示例 2：
输入 [“FrequencyTracker”, “add”, “deleteOne”, “hasFrequency”] [[], [1],[1], [1]]
输出 [null, null, null, false]
解释 FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(1); // 数据结构现在包含 [1]
frequencyTracker.deleteOne(1); // 数据结构现在为空 []
frequencyTracker.hasFrequency(1); // 返回 false ，因为数据结构为空
示例 3：
输入 [“FrequencyTracker”, “hasFrequency”, “add”, “hasFrequency”] [[],[2], [3], [1]]
输出 [null, false, null, true]
解释 FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.hasFrequency(2); // 返回 false ，因为数据结构为空
frequencyTracker.add(3); // 数据结构现在包含 [3]
frequencyTracker.hasFrequency(1); // 返回 true ，因为 3 出现 1 次
思路
一开始我想的是使用一个哈希表，key为数据结构中的值，value为出现次数，查找的时候就遍历整个哈希表看value是否与number相同就行，最后在样例中发现存在多次查找的情况，如果我们每次查找都要遍历哈希表那么复杂度太高了，于是我再使用一个哈希表key表示出现次数，value表示出现该次数的数字个数。当大于0时表示存在，小于等于0时不存在。
代码
class FrequencyTracker {
private:
unordered_map<int,int> hash;
unordered_map<int,int> hash1;
public:
FrequencyTracker() {
}
void add(int number) {
if(hash.count(number))
{
hash[number]++;
}
else
{
hash[number]=1;
}
hash1[hash[number]-1]--;
hash1[hash[number]]++;
}
void deleteOne(int number) {
if(!hash.count(number))
{
return;
}
if(hash[number]==0)
{
hash.erase(number);
}
else
{
hash[number]--;
hash1[hash[number]+1]--;
hash1[hash[number]]++;
}
}
bool hasFrequency(int frequency) {
return hash1[frequency]>0;
}
};
/**
* Your FrequencyTracker object will be instantiated and called as such:
* FrequencyTracker* obj = new FrequencyTracker();
* obj->add(number);
* obj->deleteOne(number);
* bool param_3 = obj->hasFrequency(frequency);
*/
收获
哈希表的应用