力扣每日一题 2024/3/21 频率跟踪器

题目描述

用例说明

 

思路讲解

看到统计数字频率或者出现次数很容易想到用哈希表，但是一个哈希表count将数字和数字出现次数映射起来似乎不太够，如果需要统计数字出现次数的频率的话还是需要进行一次遍历，时间复杂度为O(n)，有没有常数级获取数字出现次数的频率呢，再定义一个哈希表times，用来建立数字出现次数和数字出现次数的频率的哈希表。

在添加元素操作中，首先需要将数字和数字出现次数存储到count中，然后更新time哈希表，该数字的出现次数对应的频率加一，该数字添加之前的出现次数对应的频率减一。

删除元素同理，首先找到该数字对应的出现次数，进行减一，然后更新times哈希表，该数字对应出现次数的频率减一，该数字删除后对应的出现次数的频率加一。

代码

class FrequencyTracker {Map<Integer,Integer> count=new HashMap<>();Map<Integer,Integer> times=new HashMap<>();public FrequencyTracker() {}public void add(int number) {count.put(number,count.getOrDefault(number,0)+1);int counts=count.get(number);times.put(counts,times.getOrDefault(counts,0)+1);times.put(counts-1,times.getOrDefault(counts-1,0)-1);}public void deleteOne(int number) {if(count.getOrDefault(number,0)==0) return;count.put(number,count.getOrDefault(number,0)-1);int counts=count.get(number);times.put(counts,times.getOrDefault(counts,0)+1);times.put(counts+1,times.getOrDefault(counts+1,0)-1);}public boolean hasFrequency(int frequency) {return times.getOrDefault(frequency,0)>0;}
}/*** Your FrequencyTracker object will be instantiated and called as such:* FrequencyTracker obj = new FrequencyTracker();* obj.add(number);* obj.deleteOne(number);* boolean param_3 = obj.hasFrequency(frequency);*/

复杂度

时间复杂度O(q) q为查询次数，其余操作均为O(1)时间内访问

空间复杂度O(m) m为值域范围