# 频率跟踪器

# 题目描述:

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

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

# 解题思路:

1、需要考虑时间的限制

2、可以通过用一个数组保存频次，以传入的 number 参数为下标，调用添加、删除方法进行增删

3、可以在通过用一个数组保存频次的次数，如 5 的频次的次数是 2，那么调用添加、删除方法就需要修改一下，

比如原本 5 的频次是 2，当在 add 的时候那么就需要把 number 的旧频次删除在加新的频次次数

代码：

class FrequencyTracker {

    private int[] index;

    private int[] frequencys;

    public FrequencyTracker() {

        index = new int[100001];

        frequencys = new int[100001];

    }

    public void add(int number) {

        // 先把 number 旧的频次删除了

        --frequencys[index[number]];

        ++index[number];

        // 在把新的 number 的频次加一

        ++frequencys[index[number]];

    }

    public void deleteOne(int number) {

        if (index[number] == 0) {

            return;

        }

        // 先把 number 旧的频次删除了

        --frequencys[index[number]];

        --index[number];

        // 在把新的 number 的频次加一

        ++frequencys[index[number]];

    }

    public boolean hasFrequency(int frequency) {

        if (frequencys[frequency] > 0) {

            return true;

        }

        return false;

    }

}