题目描述
请你设计并实现一个能够对其中的值进行跟踪的数据结构,并支持对频率相关查询进行应答。
实现 FrequencyTracker
类:
FrequencyTracker()
:使用一个空数组初始化FrequencyTracker
对象。void add(int number)
:添加一个number
到数据结构中。void deleteOne(int number)
:从数据结构中删除一个number
。数据结构 可能不包含number
,在这种情况下不删除任何内容。bool hasFrequency(int frequency)
: 如果数据结构中存在出现frequency
次的数字,则返回true
,否则返回false
。
思路
使用两个哈希表,一个记录添加的数字,这个哈希表称作 freq
,另一个记录数字出现的频率,记作 freq_counter
。具体来说:
- 在添加一个数字的时候
- 首先该数字在
freq_counter
出现的次数减一; - 对
freq
中该数字出现的频率加一; - 最后对该数字在
freq_counter
出现的次数加一。
- 首先该数字在
以示例一为例,它的输入是
["FrequencyTracker", "add", "add", "hasFrequency"]
[[], [3], [3], [2]]
那么对应的 freq
和 freq_counter
为:
freq freq_counter
[] []
[3]=1 [1]=1
[3]=2 [2]=1
删除同理:
- 首先将
freq_counter
对应的频率减一; - 对
freq
对应的数字减一; - 最后将
freq_counter
对应的频率加一。
最后是 hasFrequency
,检查 freq_counter
对应的频率大于 0 即可。
对于 Python,我们可以使用 Counter 这个计数器: