扬州市建设局网站,一级a做爰全过程网站,ios开发网站app,网站 域名解析错误题目描述 用例说明 思路讲解
看到统计数字频率或者出现次数很容易想到用哈希表#xff0c;但是一个哈希表count将数字和数字出现次数映射起来似乎不太够#xff0c;如果需要统计数字出现次数的频率的话还是需要进行一次遍历#xff0c;时间复杂度为O(n)#xff0c;有没有常…题目描述 用例说明 思路讲解
看到统计数字频率或者出现次数很容易想到用哈希表但是一个哈希表count将数字和数字出现次数映射起来似乎不太够如果需要统计数字出现次数的频率的话还是需要进行一次遍历时间复杂度为O(n)有没有常数级获取数字出现次数的频率呢再定义一个哈希表times用来建立数字出现次数和数字出现次数的频率的哈希表。
在添加元素操作中首先需要将数字和数字出现次数存储到count中然后更新time哈希表该数字的出现次数对应的频率加一该数字添加之前的出现次数对应的频率减一。
删除元素同理首先找到该数字对应的出现次数进行减一然后更新times哈希表该数字对应出现次数的频率减一该数字删除后对应的出现次数的频率加一。
代码
class FrequencyTracker {MapInteger,Integer countnew HashMap();MapInteger,Integer timesnew HashMap();public FrequencyTracker() {}public void add(int number) {count.put(number,count.getOrDefault(number,0)1);int countscount.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 countscount.get(number);times.put(counts,times.getOrDefault(counts,0)1);times.put(counts1,times.getOrDefault(counts1,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为值域范围
