2671. 频率跟踪器

题目描述：

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

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

---

解题分析及思路：

思路：

解决该问题可以使用双哈希表：

• 一个哈希表用于 numberMap 记录数字出现的次数，即：key为number，value为number出现的次数；
• 一个哈希表用于 countMap 记录数字出现的次数的个数，即：key为number出现的次数，value为出现该次数的所有number的个数。

那么在添加 number 时：

• 首先，我们需要将 countMap 中 key 为 [原来number的次数] 减1；
• 需要将 numberMap 中 key 为 [number] 的次数加1；
• 最后将 countMap 中 key 为 [现在number的次数] 加1。

在删除 number 时：

• 首先，我们需要将 countMap 中 key 为 [原来number的次数] 减1；
• 需要将 numberMap 中 key 为 [number] 的次数减1；
• 最后将 countMap 中 key 为 [现在number的次数] 加1。

在查询 frequency 时：

• 我们只需要判断 countMap 中 key 为 [frequency] 的值是否大于0即可。

type FrequencyTracker struct {
	countMap  map[int]int
	numberMap map[int]int
}

func Constructor() FrequencyTracker {
	return FrequencyTracker{
		countMap:  make(map[int]int),
		numberMap: make(map[int]int),
	}
}

func (this *FrequencyTracker) Add(number int) {
	this.countMap[this.numberMap[number]]--
	this.numberMap[number]++
	this.countMap[this.numberMap[number]]++
}

func (this *FrequencyTracker) DeleteOne(number int) {
	if this.numberMap[number] == 0 {
		return
	}
	this.countMap[this.numberMap[number]]--
	this.numberMap[number]--
	this.countMap[this.numberMap[number]]++
}

func (this *FrequencyTracker) HasFrequency(frequency int) bool {
	return this.countMap[frequency] > 0
}

复杂度：

• 时间复杂度：O(1)，单次操作的复杂度为 1
• 空间复杂度：O(N)

执行结果：

• 执行耗时:320 ms,击败了100.00% 的Go用户
• 内存消耗:65.1 MB,击败了60.00% 的Go用户