初学python记录：力扣2671. 频率跟踪器

题目：

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

实现 FrequencyTracker 类：

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

思考：

增加、删除元素都能通过列表的append方法和remove方法直接解决，重点在于判断列表中是否存在出现 frequency 次的数字。

1用另一个列表记录每个数出现的次数，代码如下：

class FrequencyTracker(object):
 
    def __init__(self):
        self.nums = []
        self.cnt = [0]   # 计数列表记录每个数字的出现次数（没有一一映射，只单纯计数）
 
 
    def add(self, number):
        """
        :type number: int
        :rtype: None
        """
        c = self.nums.count(number)    # number出现的次数
        if c == 0:
            self.cnt.append(1)   # 若number没有出现过，则计数列表增加一个元素1
        else:
            index = self.cnt.index(c)   
            self.cnt[index] += 1   # 若number出现过且次数为c，则将计数列表中的一个值为c的元素加一
        self.nums.append(number)   
 
 
    def deleteOne(self, number):
        """
        :type number: int
        :rtype: None
        """
        c = self.nums.count(number)
        if c != 0:  # 只有数组中含有number才能执行删除操作
            index = self.cnt.index(c)
            self.cnt[index] -= 1   # 将计数列表中的一个值为c的元素减一
            self.nums.remove(number)
 
 
    def hasFrequency(self, frequency):
        """
        :type frequency: int
        :rtype: bool
        """
        n = len(self.cnt)
        for i in range(0, n):   # 遍历计数列表，判断是否有出现次数为frequency的数
            if self.cnt[i] == frequency:
                return True
        return False
 

测试用例通过，但提交超时。

分析超时：

1. 查找时间复杂度：

   • 列表：查找一个元素是否存在于列表中，或者获取列表中某个元素的索引（如使用count或index方法），需要遍历整个列表。在最坏的情况下，这是一个O(n)的操作，其中n是列表中元素的数量。
   • 字典：字典在Python中是通过哈希表实现的。查找一个键是否存在于字典中，或者获取一个键的值（如检查某个数字的频率），是一个平均O(1)的操作，即常数时间复杂度。

2. 插入和删除时间复杂度：

   • 列表：向列表中添加元素（如果不考虑需要先查找元素是否存在）是一个O(1)的操作，但如果需要删除一个元素（如remove方法），首先需要找到该元素的位置，这又是一个O(n)的操作。此外，删除列表中的元素可能导致列表中其他元素的位置移动，进一步增加开销。
   • 字典：在字典中添加或删除一个键-值对都是平均O(1)的操作，因为它们基于哈希表实现。

因此，当处理大量数据时，字典因其更高效的查找、插入和删除操作而具有显著的性能优势。

 下面是用字典存储每个数对应的出现次数的代码：

class FrequencyTracker(object):
 
    def __init__(self):
        self.nums = []
        self.cnt = {}   # 字典记录每个数字的出现次数（一一映射）
 
 
    def add(self, number):
        """
        :type number: int
        :rtype: None
        """
        if number in self.nums:
            self.cnt[number] += 1
        else:
            self.cnt[number] = 1
        self.nums.append(number)   
 
 
    def deleteOne(self, number):
        """
        :type number: int
        :rtype: None
        """
        if number in self.nums:  # 只有数组中含有number才能执行删除操作
            self.cnt[number] -= 1
            self.nums.remove(number)
 
 
    def hasFrequency(self, frequency):
        """
        :type frequency: int
        :rtype: bool
        """
        if frequency in self.cnt.values():
            return True
        return False
 
 

然后还是超时了。。。。。。因为调用hasFrequency方法的时候，还是要遍历字典的所有值组成的列表，时间复杂度还是O(n)。

参考题解，用两个哈希表解决这题。一个哈希表存储‘数-出现次数’的对应关系，另一个哈希表存储‘出现次数-出现次数的出现次数’。

代码如下：

class FrequencyTracker(object):
 
    def __init__(self):
        self.cnt = {}   # 一个字典记录‘每个数字-出现次数’
        self.cnt_cnt = {0:0}   # 另一个字典记录‘出现次数-出现次数的出现次数’
 
 
    def add(self, number):
        """
        :type number: int
        :rtype: None
        """
        freq = self.cnt.get(number, 0)
        self.cnt[number] = freq+1
        self.cnt_cnt[freq] -= 1
        self.cnt_cnt[freq+1] += 1
        
 
    def deleteOne(self, number):
        """
        :type number: int
        :rtype: None
        """
        if self.cnt[number] != 0:  # 只有数组中含有number才能执行删除操作
            self.cnt[number] -= 1
            self.cnt_cnt[self.cnt[number]+1] -= 1
            self.cnt_cnt[self.cnt[number]] += 1
 
 
    def hasFrequency(self, frequency):
        """
        :type frequency: int
        :rtype: bool
        """
        if self.cnt_cnt[frequency] != 0:
            return True
        return False

又报错了，我真的伤心了....

KeyError: 1 self.cnt_cnt[freq+1] += 1 

原因是在尝试对self.cnt_cnt中的某个键（出现次数）进行减法操作时，那个键可能尚不存在于字典中。这在尤其是第一次增加或删除某个数字时很常见，因为默认情况下字典中并没有为每个可能的计数初始化键。

这里要使用‘Counter’——一个特殊的字典类，用于计数可哈希对象，可以自动处理这个问题，因为Counter在访问不存在的键时会返回0而不是抛出KeyError。这意味着您可以自由地增加或减少计数而不需要预先检查键是否存在。

 代码如下：

class FrequencyTracker(object):
 
    def __init__(self):
        self.cnt = Counter()   # 一个字典记录‘每个数字-出现次数’
        self.cnt_cnt = Counter()   # 另一个字典记录‘出现次数-出现次数的出现次数’
 
 
    def add(self, number):
        """
        :type number: int
        :rtype: None
        """
        self.cnt[number] += 1   # number对应的出现次数+1
        self.cnt_cnt[self.cnt[number]-1] -= 1   # 原来的出现次数的出现次数-1
        self.cnt_cnt[self.cnt[number]] += 1   # 新的的出现次数的出现次数+1
        
 
    def deleteOne(self, number):
        """
        :type number: int
        :rtype: None
        """
        if self.cnt[number] != 0:  # 只有数组中含有number才能执行删除操作
            self.cnt[number] -= 1    # number对应的出现次数-1
            self.cnt_cnt[self.cnt[number]+1] -= 1   # 原来的出现次数的出现次数-1
            self.cnt_cnt[self.cnt[number]] += 1   # 新的的出现次数的出现次数+1
 
 
    def hasFrequency(self, frequency):
        """
        :type frequency: int
        :rtype: bool
        """
        if self.cnt_cnt[frequency] != 0:
            return True   
        return False

提交终于通过了，我快不认识“出现次数”四个字了：