2671 频率跟踪器(Medium)

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

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

双哈希

一个用来存频率，一个用来存频率的频率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
public class FrequencyTracker {
    private HashMap<Integer,Integer> hashMap;
    private TreeMap<Integer,Integer> treeMap;

    public FrequencyTracker() {
        hashMap = new HashMap<>();
        treeMap = new TreeMap<>();
    }

    public void add(int number) {
        if (!hashMap.containsKey(number)){
            hashMap.put(number,1);
            treeMap.put(1,treeMap.getOrDefault(1,0)+1);
        }
        else {
            Integer integer = hashMap.get(number);
            hashMap.put(number,integer+1);
            if (treeMap.containsKey(integer)){
                int count = treeMap.get(integer);
                if (count == 1){
                    treeMap.remove(integer);
                }
                else{
                    treeMap.replace(integer,count-1);
                }
                treeMap.put(integer+1,treeMap.getOrDefault(integer+1,0)+1);
            }
        }
    }

    public void deleteOne(int number) {

        if (hashMap.containsKey(number)){
            int i1 = hashMap.get(number);
            int temp = treeMap.get(i1);
            if (temp == 1){
                treeMap.remove(i1);
            }
            else {
                treeMap.replace(i1,temp-1);
            }
            if (i1-1 !=0){
                if (treeMap.containsKey(i1-1)){
                    treeMap.put(i1-1,treeMap.get(i1-1)+1);
                }
                else {
                    treeMap.put(i1-1,1);
                }
            }

            if (i1 == 1){
                hashMap.remove(number);
            }
            else {
                hashMap.put(number,i1-1);
            }

        }
    }

    public boolean hasFrequency(int frequency) {

        if (treeMap.containsKey(frequency)){
            int temp = treeMap.get(frequency);
            if (temp > 0){
                return true;
            }
            else {
                return false;
            }
        }
        else {
            return false;
        }
    }

    public static void main(String[] args) {
        FrequencyTracker frequencyTracker = new FrequencyTracker();

        frequencyTracker.add(2);

        frequencyTracker.add(7);

        frequencyTracker.add(7);
        frequencyTracker.add(3);
        frequencyTracker.add(3);

        frequencyTracker.deleteOne(7);
        frequencyTracker.deleteOne(7);
        System.out.println(frequencyTracker.hasFrequency(2));
        System.out.println(frequencyTracker.hasFrequency(1));
    }

}