LeetCode 题解工作台
频率跟踪器
请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。 实现 FrequencyTracker 类： FrequencyTracker() ：使用一个空数组初始化 FrequencyTracker 对象。 void add(int number) ：添加一个 number…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 哈希·表·结合·design
答案摘要
我们定义两个哈希表，其中 用于记录每个数字出现的次数，而 用于记录每个出现次数的数字的个数。 对于 `add` 操作，我们直接将哈希表 中 对应的值减一，然后将 加一，再将 对应的值加一。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·design 题型思路
题目描述
请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。
实现 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 <= 1051 <= frequency <= 105- 最多调用
add、deleteOne和hasFrequency共计2 * 105次
解题思路
方法一：哈希表
我们定义两个哈希表，其中 用于记录每个数字出现的次数，而 用于记录每个出现次数的数字的个数。
对于 add 操作，我们直接将哈希表 中 对应的值减一，然后将 加一，再将 对应的值加一。
对于 deleteOne 操作，我们首先判断 是否大于零，如果大于零，我们将哈希表 中 对应的值减一，然后将 减一，再将 对应的值加一。
对于 hasFrequency 操作，我们直接返回 是否大于零。
时间复杂度方面，由于我们使用了哈希表，因此每个操作的时间复杂度均为 。空间复杂度 ，其中 为不同的数字的个数。
class FrequencyTracker:
def __init__(self):
self.cnt = defaultdict(int)
self.freq = defaultdict(int)
def add(self, number: int) -> None:
self.freq[self.cnt[number]] -= 1
self.cnt[number] += 1
self.freq[self.cnt[number]] += 1
def deleteOne(self, number: int) -> None:
if self.cnt[number]:
self.freq[self.cnt[number]] -= 1
self.cnt[number] -= 1
self.freq[self.cnt[number]] += 1
def hasFrequency(self, frequency: int) -> bool:
return self.freq[frequency] > 0
# Your FrequencyTracker object will be instantiated and called as such:
# obj = FrequencyTracker()
# obj.add(number)
# obj.deleteOne(number)
# param_3 = obj.hasFrequency(frequency)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if the candidate correctly uses hash tables for efficient frequency management.
- question_mark
Evaluate the approach for handling multiple operations efficiently under large constraints.
- question_mark
Assess how the candidate tracks the frequency of frequencies to optimize the `hasFrequency` query.
常见陷阱
外企场景- error
Failing to handle cases where a number's frequency drops to zero after a delete operation.
- error
Using inefficient data structures that lead to time complexity issues with the large number of operations.
- error
Not correctly updating the frequency count in the second hash table for `hasFrequency` queries.
进阶变体
外企场景- arrow_right_alt
Track the frequency of multiple numbers with the ability to reset frequencies.
- arrow_right_alt
Support additional operations like `getMostFrequent()` to return the number with the highest frequency.
- arrow_right_alt
Design a version that supports querying for the least frequent number.