目标
请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。
实现 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^5
- 1 <= frequency <= 10^5
- 最多调用 add、deleteOne 和 hasFrequency 共计 2 * 10^5 次
思路
这道题要我们写一个数据结构，能够实时追踪已保存数字的出现频率。我们可以很方便地使用Map记录数字出现的频率，但是无法直接判断频率是否存在。只能遍历EntrySet一个一个找。
于是考虑再记录一个以频率为Key，相应频率的数字个数为value的Map，以便直接判断是否存在相应的频率。
那么第一个Map是否可以省略呢？当然不行，因为数字新增或删除后，相应的频率也会发生变化。如果不记录的话，无法更新第二个Map。
当数字出现频率增加，除了要累加第一个Map相应数字的频率，还要同时将第二个Map原频率对应数字的个数减1，新频率对应数字的个数加1。
当数字出现频率减少，除了要减小第一个Map相应数字的频率，还要同时将第二个Map原频率对应数字的个数减1，新频率对应数字的个数加1。
代码
/**
* @date 2024-03-21 8:57
*/
public class FrequencyTracker2671 {
class FrequencyTracker {
private final Map<Integer, Integer> elements;
private final Map<Integer, Integer> fRecord;
public FrequencyTracker() {
elements = new HashMap<>();
fRecord = new HashMap<>();
}
public void add(int number) {
Integer f = elements.get(number) == null ? 0 : elements.get(number);
if (f != 0) {
fRecord.put(f, fRecord.get(f) - 1);
}
elements.merge(number, 1, Integer::sum);
fRecord.merge(++f, 1, Integer::sum);
}
public void deleteOne(int number) {
Integer f = elements.get(number) == null ? 0 : elements.get(number);
if (f != 0) {
elements.put(number, f - 1);
fRecord.put(f, fRecord.get(f) - 1);
fRecord.merge(--f, 1, Integer::sum);
}
}
public boolean hasFrequency(int frequency) {
return fRecord.get(frequency) != null && fRecord.get(frequency) > 0;
}
}
性能
有网友写的变长数组性能更高一些，如果是直接根据题目最大范围创建数组，针对这些测试案例性能反而不好。
