本文最后更新于 191 天前,其中的信息可能已经有所发展或是发生改变。
请你设计并实现一个能够对其中的值进行跟踪的数据结构,并支持对频率相关查询进行应答。
实现 FrequencyTracker
类:
FrequencyTracker()
:使用一个空数组初始化FrequencyTracker
对象。void add(int number)
:添加一个number
到数据结构中。void deleteOne(int number)
:从数据结构中删除一个number
。数据结构 可能不包含number
,在这种情况下不删除任何内容。bool hasFrequency(int frequency)
: 如果数据结构中存在出现frequency
次的数字,则返回true
,否则返回false
。
示例 :
输入
[“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 次
解(双哈希表)
from collections import Counter
class FrequencyTracker:
def __init__(self):
self.freq = Counter() # number的出现频率
self.freq_cnt = Counter() # 各个频率出现的次数
def add(self, number):
self.freq_cnt[self.freq[number]] -= 1
self.freq[number] += 1
self.freq_cnt[self.freq[number]] += 1
def deleteOne(self, number):
if self.freq[number] == 0:
return
self.freq_cnt[self.freq[number]] -= 1
self.freq[number] -= 1
self.freq_cnt[self.freq[number]] += 1
def hasFrequency(self, frequency):
return self.freq_cnt[frequency] > 0
# [[], [2], [3], [1]]
# frequencyTracker = FrequencyTracker()
# x = frequencyTracker.hasFrequency(2)
# y = frequencyTracker.add(3)
# z = frequencyTracker.hasFrequency(1)
# print(x,y,z)