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 <= 105
• 1 <= frequency <= 105
• 最多调用 add、deleteOne 和 hasFrequency 共计 2 * 105 次

本题视频讲解

见【周赛 344】 第二题，欢迎点赞投币！

思路

用哈希表 cnt 统计每个数的出现次数。

用哈希表 freq 统计出现次数的出现次数，从而可以 \mathcal{O}(1) 回答 hasFrequency。

添加删除元素的时候，除了修改 cnt}[\textit{number}]，还需要根据 cnt}[\textit{number}] 的变化来修改 freq，具体见代码。

[sol1-Python3]

class FrequencyTracker:
    def __init__(self):
        self.cnt = Counter()  # 每个数的出现次数
        self.freq = Counter()  # 出现次数的出现次数

    def add(self, number: int) -> None:
        self.freq[self.cnt[number]] -= 1  # 直接减，因为下面询问的不会涉及到 frequency=0
        self.cnt[number] += 1
        self.freq[self.cnt[number]] += 1

    def deleteOne(self, number: int) -> None:
        if self.cnt[number] == 0: return  # 不删除任何内容
        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

[sol1-Java]

class FrequencyTracker {
    private Map<Integer, Integer> cnt = new HashMap<>(); // 每个数的出现次数
    private Map<Integer, Integer> freq = new HashMap<>(); // 出现次数的出现次数

    public FrequencyTracker() {}

    public void add(int number) {
        // 直接减，因为下面询问的不会涉及到 frequency=0
        freq.merge(cnt.getOrDefault(number, 0), -1, Integer::sum);
        int c = cnt.merge(number, 1, Integer::sum);
        freq.merge(c, 1, Integer::sum);
    }

    public void deleteOne(int number) {
        if (cnt.getOrDefault(number, 0) == 0) return; // 不删除任何内容
        freq.merge(cnt.get(number), -1, Integer::sum);
        int c = cnt.merge(number, -1, Integer::sum);
        freq.merge(c, 1, Integer::sum);
    }

    public boolean hasFrequency(int frequency) {
        return freq.getOrDefault(frequency, 0) > 0;
    }
}

[sol1-C++]

class FrequencyTracker {
    unordered_map<int, int> cnt; // 每个数的出现次数
    unordered_map<int, int> freq; // 出现次数的出现次数
public:
    FrequencyTracker() {}

    void add(int number) {
        --freq[cnt[number]]; // 直接减，因为下面询问的不会涉及到 frequency=0
        ++freq[++cnt[number]];
    }

    void deleteOne(int number) {
        if (!cnt[number]) return; // 不删除任何内容
        --freq[cnt[number]];
        ++freq[--cnt[number]];
    }

    bool hasFrequency(int frequency) {
        return freq[frequency];
    }
};

[sol1-Go]

type FrequencyTracker struct {
	cnt  map[int]int // 每个数的出现次数
	freq map[int]int // 出现次数的出现次数
}

func Constructor() (_ FrequencyTracker) {
	return FrequencyTracker{map[int]int{}, map[int]int{} }
}

func (f FrequencyTracker) Add(number int) {
	f.freq[f.cnt[number]]-- // 直接减，因为下面询问的不会涉及到 frequency=0
	f.cnt[number]++
	f.freq[f.cnt[number]]++
}

func (f FrequencyTracker) DeleteOne(number int) {
	if f.cnt[number] == 0 {
		return // 不删除任何内容
	}
	f.freq[f.cnt[number]]--
	f.cnt[number]--
	f.freq[f.cnt[number]]++
}

func (f FrequencyTracker) HasFrequency(frequency int) bool {
	return f.freq[frequency] > 0
}

复杂度分析

• 时间复杂度：所有操作均为 \mathcal{O}(1)。
• 空间复杂度：\mathcal{O}(q)。其中 q 为操作次数。