频率跟踪器

难度: 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 次

示例 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 次

提示：

1 <= number <= 10⁵
1 <= frequency <= 10⁵
最多调用 add、deleteOne 和 hasFrequency 共计 2 * 10⁵ 次

Submission

运行时间: 314 ms

内存: 76.0 MB

class FrequencyTracker:

    def __init__(self):
        self.dict = {}
        self.count = {}

    def add(self, number: int) -> None:
        if number in self.dict:
            if self.dict[number] > 0:
                self.count[self.dict[number]] -= 1
            self.dict[number] += 1
            self.count[self.dict[number]] = self.count.get(self.dict[number], 0)+1
        else:
            self.dict[number] = 1
            self.count[1] = self.count.get(1, 0)+1


    def deleteOne(self, number: int) -> None:
        if number in self.dict:
            if self.dict[number] > 0:
                self.count[self.dict[number]] -= 1
            self.dict[number] = max(0, self.dict[number]-1)
            if self.dict[number] > 0:
                self.count[self.dict[number]] += 1

    def hasFrequency(self, frequency: int) -> bool:
        if frequency not in self.count:
            return False
        return self.count[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)

Explain

设计一个 'FrequencyTracker' 类，用于跟踪和查询数字的频率。这个类使用两个字典：'dict' 存储每个数字出现的次数，'count' 存储每个出现次数对应的数字的个数。在 'add' 方法中，增加数字的出现次数，并相应更新每个频率的计数。在 'deleteOne' 方法中，减少数字的出现次数，并更新频率计数。'hasFrequency' 方法检查是否有数字的出现次数等于给定的频率。

时间复杂度: O(1)

空间复杂度: O(n)

class FrequencyTracker:

    def __init__(self):
        self.dict = {}  # 存储每个数字的频率
        self.count = {}  # 存储每个频率对应的数字数量

    def add(self, number: int) -> None:
        # 如果数字已存在，更新其频率
        if number in self.dict:
            # 减少当前频率的计数
            if self.dict[number] > 0:
                self.count[self.dict[number]] -= 1
            # 增加数字的频率
            self.dict[number] += 1
            # 增加新频率的计数
            self.count[self.dict[number]] = self.count.get(self.dict[number], 0) + 1
        else:
            # 如果是新数字，初始化频率为1
            self.dict[number] = 1
            self.count[1] = self.count.get(1, 0) + 1

    def deleteOne(self, number: int) -> None:
        # 如果数字存在，减少其频率
        if number in self.dict:
            # 减少当前频率的计数
            if self.dict[number] > 0:
                self.count[self.dict[number]] -= 1
            # 减少数字的频率
            self.dict[number] = max(0, self.dict[number] - 1)
            # 如果频率仍大于0，增加新频率的计数
            if self.dict[number] > 0:
                self.count[self.dict[number]] += 1

    def hasFrequency(self, frequency: int) -> bool:
        # 检查是否有数字的出现次数等于给定频率
        if frequency not in self.count:
            return False
        return self.count[frequency] > 0

Explore

是的，从`dict`字典中移除频率为0的数字是一个好做法。这样做可以避免字典无限增长，特别是在处理大量数据时。此外，删除这些数据可以避免对内存的不必要消耗，并且可以保持`dict`字典的准确性，确保只包含活跃的数据项。

是的，在多线程环境下，不同的线程可能同时修改同一个数字的频率，这可能会导致`self.count`的更新不一致或出错。为了防止这种情况，可以通过锁机制来确保每次只有一个线程能够修改`dict`和`count`，或者使用线程安全的数据结构来管理这些数据。

在`hasFrequency`方法中，使用`self.count[frequency] > 0`是为了确认不仅`frequency`键存在于`count`字典中，而且对应的频率计数大于0，即确实有数字的频率正好等于查询的频率。仅检查键是否存在可能导致错误的返回结果，因为即使键存在，其对应的计数可能为0，意味着没有任何数字的当前频率是该值。

在实现`FrequencyTracker`时，应该增加输入验证来确保只处理有效的整数输入。对于意外或无效输入（如负数、字符串或非整数），可以通过抛出异常或返回特定的错误信息来处理。这样可以保证`FrequencyTracker`的稳定性和可靠性，避免因错误输入导致的程序错误或崩溃。