Description#
Design a data structure that keeps track of the values in it and answers some queries regarding their frequencies.
Implement the FrequencyTracker class.
FrequencyTracker(): Initializes the FrequencyTracker object with an empty array initially.void add(int number): Adds number to the data structure.void deleteOne(int number): Deletes one occurrence of number from the data structure. The data structure may not contain number, and in this case nothing is deleted.bool hasFrequency(int frequency): Returns true if there is a number in the data structure that occurs frequency number of times, otherwise, it returns false.
Example 1:
Input
["FrequencyTracker", "add", "add", "hasFrequency"]
[[], [3], [3], [2]]
Output
[null, null, null, true]
Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(3); // The data structure now contains [3]
frequencyTracker.add(3); // The data structure now contains [3, 3]
frequencyTracker.hasFrequency(2); // Returns true, because 3 occurs twice
Example 2:
Input
["FrequencyTracker", "add", "deleteOne", "hasFrequency"]
[[], [1], [1], [1]]
Output
[null, null, null, false]
Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(1); // The data structure now contains [1]
frequencyTracker.deleteOne(1); // The data structure becomes empty []
frequencyTracker.hasFrequency(1); // Returns false, because the data structure is empty
Example 3:
Input
["FrequencyTracker", "hasFrequency", "add", "hasFrequency"]
[[], [2], [3], [1]]
Output
[null, false, null, true]
Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.hasFrequency(2); // Returns false, because the data structure is empty
frequencyTracker.add(3); // The data structure now contains [3]
frequencyTracker.hasFrequency(1); // Returns true, because 3 occurs once
Constraints:
1 <= number <= 1051 <= frequency <= 105- At most,
2 * 105 calls will be made to add, deleteOne, and hasFrequency in total.
Solutions#
Solution 1#
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
| class FrequencyTracker:
def __init__(self):
self.cnt = defaultdict(int)
self.freq = defaultdict(int)
def add(self, number: int) -> None:
if self.freq[self.cnt[number]] > 0:
self.freq[self.cnt[number]] -= 1
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
# Your FrequencyTracker object will be instantiated and called as such:
# obj = FrequencyTracker()
# obj.add(number)
# obj.deleteOne(number)
# param_3 = obj.hasFrequency(frequency)
|
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
| class FrequencyTracker {
private Map<Integer, Integer> cnt = new HashMap<>();
private Map<Integer, Integer> freq = new HashMap<>();
public FrequencyTracker() {
}
public void add(int number) {
int f = cnt.getOrDefault(number, 0);
if (freq.getOrDefault(f, 0) > 0) {
freq.merge(f, -1, Integer::sum);
}
cnt.merge(number, 1, Integer::sum);
freq.merge(f + 1, 1, Integer::sum);
}
public void deleteOne(int number) {
int f = cnt.getOrDefault(number, 0);
if (f == 0) {
return;
}
freq.merge(f, -1, Integer::sum);
cnt.merge(number, -1, Integer::sum);
freq.merge(f - 1, 1, Integer::sum);
}
public boolean hasFrequency(int frequency) {
return freq.getOrDefault(frequency, 0) > 0;
}
}
/**
* Your FrequencyTracker object will be instantiated and called as such:
* FrequencyTracker obj = new FrequencyTracker();
* obj.add(number);
* obj.deleteOne(number);
* boolean param_3 = obj.hasFrequency(frequency);
*/
|
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
| class FrequencyTracker {
public:
FrequencyTracker() {
}
void add(int number) {
int f = cnt[number];
if (f > 0) {
freq[f]--;
}
cnt[number]++;
freq[f + 1]++;
}
void deleteOne(int number) {
int f = cnt[number];
if (f == 0) {
return;
}
freq[f]--;
cnt[number]--;
freq[f - 1]++;
}
bool hasFrequency(int frequency) {
return freq[frequency] > 0;
}
private:
unordered_map<int, int> cnt;
unordered_map<int, int> freq;
};
/**
* Your FrequencyTracker object will be instantiated and called as such:
* FrequencyTracker* obj = new FrequencyTracker();
* obj->add(number);
* obj->deleteOne(number);
* bool param_3 = obj->hasFrequency(frequency);
*/
|
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
| type FrequencyTracker struct {
cnt map[int]int
freq map[int]int
}
func Constructor() FrequencyTracker {
return FrequencyTracker{map[int]int{}, map[int]int{}}
}
func (this *FrequencyTracker) Add(number int) {
f := this.cnt[number]
if f > 0 {
this.freq[f]--
}
this.cnt[number]++
this.freq[f+1]++
}
func (this *FrequencyTracker) DeleteOne(number int) {
f := this.cnt[number]
if f == 0 {
return
}
this.freq[f]--
this.cnt[number]--
this.freq[f-1]++
}
func (this *FrequencyTracker) HasFrequency(frequency int) bool {
return this.freq[frequency] > 0
}
/**
* Your FrequencyTracker object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(number);
* obj.DeleteOne(number);
* param_3 := obj.HasFrequency(frequency);
*/
|
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
| class FrequencyTracker {
private cnt: Map<number, number>;
private freq: Map<number, number>;
constructor() {
this.cnt = new Map();
this.freq = new Map();
}
add(number: number): void {
const f = this.cnt.get(number) || 0;
if (f > 0) {
this.freq.set(f, (this.freq.get(f) || 0) - 1);
}
this.cnt.set(number, f + 1);
this.freq.set(f + 1, (this.freq.get(f + 1) || 0) + 1);
}
deleteOne(number: number): void {
const f = this.cnt.get(number) || 0;
if (f === 0) {
return;
}
this.freq.set(f, (this.freq.get(f) || 0) - 1);
this.cnt.set(number, f - 1);
this.freq.set(f - 1, (this.freq.get(f - 1) || 0) + 1);
}
hasFrequency(frequency: number): boolean {
return (this.freq.get(frequency) || 0) > 0;
}
}
/**
* Your FrequencyTracker object will be instantiated and called as such:
* var obj = new FrequencyTracker()
* obj.add(number)
* obj.deleteOne(number)
* var param_3 = obj.hasFrequency(frequency)
*/
|
