当前位置：首页 > news >正文

LeetCode 2671.频率跟踪器：俩计数哈希表

news 2025/8/18 15:09:47

【LetMeFly】2671.频率跟踪器：俩计数哈希表

力扣题目链接：https://leetcode.cn/problems/frequency-tracker/

请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。

实现 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 次

提示：

1 <= number <= 10⁵
1 <= frequency <= 10⁵
最多调用 add、deleteOne 和 hasFrequency 共计 2 * 10⁵ 次

方法一：俩计数哈希表

使用一个哈希表val2times记录值val一共出现了多少次。
使用一个哈希表times2times记录val2times中的每个times一共出现了多少次。

添加或删除元素时，更新val2times[val]的值，并更新times2times[val2times[val] (+diff)]的值。

询问是否存在出现了frequency次的数字时，直接返回times2times[frequency]是否非零。

时间复杂度 $O (1) / 操作$
空间复杂度 $O (n)$

AC代码

C++

class FrequencyTracker {
private:unordered_map<int, int> val2times, times2times;
public:FrequencyTracker() {}void add(int number, int diff=1) {int originalTimes = val2times[number];val2times[number] += diff;times2times[originalTimes]--;times2times[originalTimes + diff]++;}void deleteOne(int number) {if (val2times[number]) {add(number, -1);}}bool hasFrequency(int frequency) {return times2times[frequency];}
};

Python

# from collections import defaultdictclass FrequencyTracker:def __init__(self):self.val2times = defaultdict(int)self.times2times = defaultdict(int)def add(self, number: int, diff=1) -> None:originalTimes = self.val2times[number]self.val2times[number] += diffself.times2times[originalTimes] -= 1self.times2times[originalTimes + diff] += 1def deleteOne(self, number: int) -> None:if self.val2times[number]:self.add(number, -1)def hasFrequency(self, frequency: int) -> bool:return self.times2times[frequency] != 0