2671. 频率跟踪器

题目描述

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

实现 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 这个计数器：

from collections import Counter
 
class FrequencyTracker:
 
    def __init__(self):
        self.freq = Counter()
        self.freq_counter = Counter()
 
    def add(self, number: int) -> None:
        self.freq_counter[self.freq[number]] -= 1
        self.freq[number] += 1
        self.freq_counter[self.freq[number]] += 1
 
    def deleteOne(self, number: int) -> None:
        if self.freq[number]==0:
            return
        self.freq_counter[self.freq[number]] -= 1
        self.freq[number] -= 1
        self.freq_counter[self.freq[number]] += 1
 
    def hasFrequency(self, frequency: int) -> bool:
        return self.freq_counter[frequency] > 0