双哈希统计，LeetCode 2671. 频率跟踪器

一、题目

1、题目描述

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

实现 FrequencyTracker 类：

• FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。
• void add(int number)：添加一个 number 到数据结构中。
• void deleteOne(int number)：从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。
• bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。

2、接口描述

python3

class FrequencyTracker:
 
    def __init__(self):
 
 
    def add(self, number: int) -> None:
 
 
    def deleteOne(self, number: int) -> None:
 
 
    def hasFrequency(self, frequency: int) -> bool:
 
 
 
# Your FrequencyTracker object will be instantiated and called as such:
# obj = FrequencyTracker()
# obj.add(number)
# obj.deleteOne(number)
# param_3 = obj.hasFrequency(frequency)

​cpp

class FrequencyTracker {
public:
    FrequencyTracker() {
 
    }
    
    void add(int number) {
 
    }
    
    void deleteOne(int number) {
 
    }
    
    bool hasFrequency(int frequency) {
 
    }
};
 
/**
 * 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);
 */

3、原题链接

2671. 频率跟踪器

---

二、解题报告

1、思路分析

2、复杂度

时间复杂度： 单词操作O(1)空间复杂度：O(n)，n为操作次数

3、代码详解

​python3

class FrequencyTracker:
 
    def __init__(self):
        self.cnt = Counter()
        self.freq = Counter()
 
    def add(self, number: int, delta = 1) -> None:
        self.freq[self.cnt[number]] -= 1
        self.cnt[number] += delta
        self.freq[self.cnt[number]] += 1
 
    def deleteOne(self, number: int) -> None:
        if self.cnt[number]:
            self.add(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)

cpp

class FrequencyTracker {
public:
    unordered_map<int, int> cnt, freq;
    FrequencyTracker() {
 
    }
    
    void add(int number) {
        freq[cnt[number]]--, freq[++cnt[number]]++;
    }
    
    void deleteOne(int number) {
        if(cnt[number])
            freq[cnt[number]]--, freq[--cnt[number]]++;
    }
    
    bool hasFrequency(int frequency) {
        return freq[frequency] > 0;
    }
};
 
/**
 * 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);
 */