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：

输入
["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 <= number <= 10^5
  • 1 <= frequency <= 10^5
  • 总共最多会对 add、deleteOne 和 hasFrequency 进行 2 * 10^5 次调用。

解题思路

解题思路

这道题要求我们设计一个数据结构来跟踪数字的频率并支持频率查询。核心思路是使用双哈希表来同时维护"数字→频率"和"频率→计数"的映射关系。

核心想法：

  1. 用一个哈希表 numFreq 记录每个数字当前的出现次数
  2. 用另一个哈希表 freqCount 记录每个频率值有多少个数字拥有这个频率
  3. 在添加或删除数字时，同时更新这两个哈希表，保持它们同步

具体操作：

  • add(number)：将 number 的频率加1，同时更新频率统计
  • deleteOne(number)：将 number 的频率减1（如果存在），同时更新频率统计
  • hasFrequency(frequency)：直接查询 freqCount[frequency] > 0

关键点是保持两个哈希表的同步：

  • 当某个数字的频率从 f 变为 f+1 时，需要将 freqCount[f] 减1，freqCount[f+1] 加1
  • 当某个频率的计数变为0时，可以将其从哈希表中删除以节省空间

这种双哈希表的设计使得所有操作都能在 O(1) 时间内完成，空间复杂度也是最优的。

代码实现

class FrequencyTracker {
private:
    unordered_map<int, int> numFreq;    // number -> frequency
    unordered_map<int, int> freqCount;  // frequency -> count
    
public:
    FrequencyTracker() {
        
    }
    
    void add(int number) {
        int oldFreq = numFreq[number];
        int newFreq = oldFreq + 1;
        numFreq[number] = newFreq;
        
        // Update frequency count
        if (oldFreq > 0) {
            freqCount[oldFreq]--;
            if (freqCount[oldFreq] == 0) {
                freqCount.erase(oldFreq);
            }
        }
        freqCount[newFreq]++;
    }
    
    void deleteOne(int number) {
        if (numFreq.find(number) == numFreq.end() || numFreq[number] == 0) {
            return;
        }
        
        int oldFreq = numFreq[number];
        int newFreq = oldFreq - 1;
        
        // Update frequency count
        freqCount[oldFreq]--;
        if (freqCount[oldFreq] == 0) {
            freqCount.erase(oldFreq);
        }
        
        if (newFreq == 0) {
            numFreq.erase(number);
        } else {
            numFreq[number] = newFreq;
            freqCount[newFreq]++;
        }
    }
    
    bool hasFrequency(int frequency) {
        return freqCount.find(frequency) != freqCount.end() && freqCount[frequency] > 0;
    }
};

class FrequencyTracker:

    def __init__(self):
        self.num_freq = {}    # number -> frequency
        self.freq_count = {}  # frequency -> count

    def add(self, number: int) -> None:
        old_freq = self.num_freq.get(number, 0)
        new_freq = old_freq + 1
        self.num_freq[number] = new_freq
        
        # Update frequency count
        if old_freq > 0:
            self.freq_count[old_freq] -= 1
            if self.freq_count[old_freq] == 0:
                del self.freq_count[old_freq]
        
        self.freq_count[new_freq] = self.freq_count.get(new_freq, 0) + 1

    def deleteOne(self, number: int) -> None:
        if number not in self.num_freq or self.num_freq[number] == 0:
            return
        
        old_freq = self.num_freq[number]
        new_freq = old_freq - 1
        
        # Update frequency count
        self.freq_count[old_freq] -= 1
        if self.freq_count[old_freq] == 0:
            del self.freq_count[old_freq]
        
        if new_freq == 0:
            del self.num_freq[number]
        else:
            self.num_freq[number] = new_freq
            self.freq_count[new_freq] = self.freq_count.get(new_freq, 0) + 1

    def hasFrequency(self, frequency: int) -> bool:
        return self.freq_count.get(frequency, 0) > 0

public class FrequencyTracker {
    private Dictionary<int, int> numFreq;    // number -> frequency
    private Dictionary<int, int> freqCount;  // frequency -> count

    public FrequencyTracker() {
        numFreq = new Dictionary<int, int>();
        freqCount = new Dictionary<int, int>();
    }
    
    public void Add(int number) {
        int oldFreq = numFreq.GetValueOrDefault(number, 0);
        int newFreq = oldFreq + 1;
        numFreq[number] = newFreq;
        
        // Update frequency count
        if (oldFreq > 0) {
            freqCount[oldFreq]--;
            if (freqCount[oldFreq] == 0) {
                freqCount.Remove(oldFreq);
            }
        }
        freqCount[newFreq] = freqCount.GetValueOrDefault(newFreq, 0) + 1;
    }
    
    public void DeleteOne(int number) {
        if (!numFreq.ContainsKey(number) || numFreq[number] == 0) {
            return;
        }
        
        int oldFreq = numFreq[number];
        int newFreq = oldFreq - 1;
        
        // Update frequency count
        freqCount[oldFreq]--;
        if (freqCount[oldFreq] == 0) {
            freqCount.Remove(oldFreq);
        }
        
        if (newFreq == 0) {
            numFreq.Remove(number);
        } else {
            numFreq[number] = newFreq;
            freqCount[newFreq] = freqCount.GetValueOrDefault(newFreq, 0) + 1;
        }
    }
    
    public bool HasFrequency(int frequency) {
        return freqCount.GetValueOrDefault(frequency, 0) > 0;
    }
}

var FrequencyTracker = function() {
    this.numFreq = new Map();
    this.freqCount = new Map();
};

FrequencyTracker.prototype.add = function(number) {
    const oldFreq = this.numFreq.get(number) || 0;
    const newFreq = oldFreq + 1;
    
    this.numFreq.set(number, newFreq);
    
    if (oldFreq > 0) {
        this.freqCount.set(oldFreq, this.freqCount.get(oldFreq) - 1);
        if (this.freqCount.get(oldFreq) === 0) {
            this.freqCount.delete(oldFreq);
        }
    }
    
    this.freqCount.set(newFreq, (this.freqCount.get(newFreq) || 0) + 1);
};

FrequencyTracker.prototype.deleteOne = function(number) {
    const oldFreq = this.numFreq.get(number) || 0;
    if (oldFreq === 0) return;
    
    const newFreq = oldFreq - 1;
    
    this.freqCount.set(oldFreq, this.freqCount.get(oldFreq) - 1);
    if (this.freqCount.get(oldFreq) === 0) {
        this.freqCount.delete(oldFreq);
    }
    
    if (newFreq === 0) {
        this.numFreq.delete(number);
    } else {
        this.numFreq.set(number, newFreq);
        this.freqCount.set(newFreq, (this.freqCount.get(newFreq) || 0) + 1);
    }
};

FrequencyTracker.prototype.hasFrequency = function(frequency) {
    return this.freqCount.has(frequency) && this.freqCount.get(frequency) > 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
addO(1)O(n)
deleteOneO(1)O(n)
hasFrequencyO(1)O(n)

其中 n 是不同数字的个数。空间复杂度主要由两个哈希表占用，在最坏情况下需要存储所有出现过的数字及其对应的频率信息。