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 containnumber, 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 <= 105
1 <= frequency <= 105
At most, 2 * 105 calls will be made to add, deleteOne, and hasFrequency in total.
Solutions
Solution 1: Hash Table
We define two hash tables, where $cnt$ is used to record the occurrence count of each number, and $freq$ is used to record the count of numbers with each frequency.
For the add operation, we directly decrement the value corresponding to $cnt[number]$ in the hash table $freq$, then increment $cnt[number]$, and finally increment the value corresponding to $cnt[number]$ in $freq$.
For the deleteOne operation, we first check if $cnt[number]$ is greater than zero. If it is, we decrement the value corresponding to $cnt[number]$ in the hash table $freq$, then decrement $cnt[number]$, and finally increment the value corresponding to $cnt[number]$ in $freq$.
For the hasFrequency operation, we directly return whether $freq[frequency]$ is greater than zero.
In terms of time complexity, since we use hash tables, the time complexity of each operation is $O(1)$. The space complexity is $O(n)$, where $n$ is the number of distinct numbers.
1 2 3 4 5 6 7 8 910111213141516171819202122232425
classFrequencyTracker:def__init__(self):self.cnt=defaultdict(int)self.freq=defaultdict(int)defadd(self,number:int)->None:self.freq[self.cnt[number]]-=1self.cnt[number]+=1self.freq[self.cnt[number]]+=1defdeleteOne(self,number:int)->None:ifself.cnt[number]:self.freq[self.cnt[number]]-=1self.cnt[number]-=1self.freq[self.cnt[number]]+=1defhasFrequency(self,frequency:int)->bool:returnself.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)
classFrequencyTracker{privateMap<Integer,Integer>cnt=newHashMap<>();privateMap<Integer,Integer>freq=newHashMap<>();publicFrequencyTracker(){}publicvoidadd(intnumber){freq.merge(cnt.getOrDefault(number,0),-1,Integer::sum);cnt.merge(number,1,Integer::sum);freq.merge(cnt.get(number),1,Integer::sum);}publicvoiddeleteOne(intnumber){if(cnt.getOrDefault(number,0)>0){freq.merge(cnt.get(number),-1,Integer::sum);cnt.merge(number,-1,Integer::sum);freq.merge(cnt.get(number),1,Integer::sum);}}publicbooleanhasFrequency(intfrequency){returnfreq.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); */
classFrequencyTracker{public:FrequencyTracker(){}voidadd(intnumber){freq[cnt[number]]--;cnt[number]++;freq[cnt[number]]++;}voiddeleteOne(intnumber){if(cnt[number]){freq[cnt[number]]--;cnt[number]--;freq[cnt[number]]++;}}boolhasFrequency(intfrequency){returnfreq[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); */
typeFrequencyTrackerstruct{cntmap[int]intfreqmap[int]int}funcConstructor()FrequencyTracker{returnFrequencyTracker{map[int]int{},map[int]int{}}}func(this*FrequencyTracker)Add(numberint){this.freq[this.cnt[number]]--this.cnt[number]++this.freq[this.cnt[number]]++}func(this*FrequencyTracker)DeleteOne(numberint){ifthis.cnt[number]>0{this.freq[this.cnt[number]]--this.cnt[number]--this.freq[this.cnt[number]]++}}func(this*FrequencyTracker)HasFrequency(frequencyint)bool{returnthis.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); */
classFrequencyTracker{privatecnt:Map<number,number>;privatefreq:Map<number,number>;constructor(){this.cnt=newMap();this.freq=newMap();}add(number:number):void{constf=this.cnt.get(number)||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{constf=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);}}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) */
usestd::collections::HashMap;structFrequencyTracker{cnt:HashMap<i32,i32>,freq:HashMap<i32,i32>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implFrequencyTracker{fnnew()->Self{FrequencyTracker{cnt:HashMap::new(),freq:HashMap::new(),}}fnadd(&mutself,number:i32){letcount=self.cnt.entry(number).or_insert(0);letprev_freq=self.freq.entry(*count).or_insert(0);*prev_freq-=1;*count+=1;letnew_freq=self.freq.entry(*count).or_insert(0);*new_freq+=1;}fndelete_one(&mutself,number:i32){ifletSome(count)=self.cnt.get_mut(&number){if*count>0{ifletSome(prev_freq)=self.freq.get_mut(count){*prev_freq-=1;}*count-=1;ifletSome(new_freq)=self.freq.get_mut(count){*new_freq+=1;}}}}fnhas_frequency(&self,frequency:i32)->bool{self.freq.get(&frequency).map_or(false,|&freq|freq>0)}}