网站开发进度计划是什么,专业做酒类营销的网站,wordpress完整虚拟资源下载类源码,app拉新任务平台【LetMeFly】2671.频率跟踪器#xff1a;俩计数哈希表
力扣题目链接#xff1a;https://leetcode.cn/problems/frequency-tracker/
请你设计并实现一个能够对其中的值进行跟踪的数据结构#xff0c;并支持对频率相关查询进行应答。
实现 FrequencyTracker 类#xff1a;…【LetMeFly】2671.频率跟踪器俩计数哈希表
力扣题目链接https://leetcode.cn/problems/frequency-tracker/
请你设计并实现一个能够对其中的值进行跟踪的数据结构并支持对频率相关查询进行应答。
实现 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 1051 frequency 105最多调用 add、deleteOne 和 hasFrequency 共计 2 * 105 次
方法一俩计数哈希表
使用一个哈希表val2times记录值val一共出现了多少次。使用一个哈希表times2times记录val2times中的每个times一共出现了多少次。
添加或删除元素时更新val2times[val]的值并更新times2times[val2times[val] (diff)]的值。
询问是否存在出现了frequency次的数字时直接返回times2times[frequency]是否非零。
时间复杂度 O ( 1 ) / 操作 O(1)/操作 O(1)/操作空间复杂度 O ( n ) O(n) O(n)
AC代码
C
class FrequencyTracker {
private:unordered_mapint, int val2times, times2times;
public:FrequencyTracker() {}void add(int number, int diff1) {int originalTimes val2times[number];val2times[number] diff;times2times[originalTimes]--;times2times[originalTimes diff];}void deleteOne(int number) {if (val2times[number]) {add(number, -1);}}bool hasFrequency(int frequency) {return times2times[frequency];}
};Python
# from collections import defaultdictclass FrequencyTracker:def __init__(self):self.val2times defaultdict(int)self.times2times defaultdict(int)def add(self, number: int, diff1) - None:originalTimes self.val2times[number]self.val2times[number] diffself.times2times[originalTimes] - 1self.times2times[originalTimes diff] 1def deleteOne(self, number: int) - None:if self.val2times[number]:self.add(number, -1)def hasFrequency(self, frequency: int) - bool:return self.times2times[frequency] ! 0同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136922983
