2671.频率跟踪器

【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 <= 105
  • 1 <= frequency <= 105
  • 最多调用 adddeleteOnehasFrequency 共计 2 * 105

方法一:俩计数哈希表

  • 使用一个哈希表val2times记录值val一共出现了多少次。
  • 使用一个哈希表times2times记录val2times中的每个times一共出现了多少次。

添加或删除元素时,更新val2times[val]的值,并更新times2times[val2times[val] (+diff)]的值。

询问是否存在出现了frequency次的数字时,直接返回times2times[frequency]是否非零。

  • 时间复杂度$O(1)/操作$
  • 空间复杂度$O(n)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class FrequencyTracker {
private:
unordered_map<int, int> val2times, times2times;
public:
FrequencyTracker() {

}

void add(int number, int diff=1) {
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# from collections import defaultdict

class FrequencyTracker:

def __init__(self):
self.val2times = defaultdict(int)
self.times2times = defaultdict(int)

def add(self, number: int, diff=1) -> None:
originalTimes = self.val2times[number]
self.val2times[number] += diff
self.times2times[originalTimes] -= 1
self.times2times[originalTimes + diff] += 1

def 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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136922983


2671.频率跟踪器
https://blog.letmefly.xyz/2024/03/21/LeetCode 2671.频率跟踪器/
作者
Tisfy
发布于
2024年3月21日
许可协议