6417. 频率跟踪器
请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。
实现 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 <= 105add、deleteOne 和 hasFrequency 共计 2 * 105 次原站题解
cpp 解法, 执行用时: 406 ms, 内存消耗: 199.2 MB, 提交时间: 2024-03-21 09:21:27
class FrequencyTracker {
unordered_map<int, int> cnt; // number 的出现次数
unordered_map<int, int> freq; // number 的出现次数的出现次数
public:
FrequencyTracker() {}
void add(int number) {
--freq[cnt[number]]; // 去掉一个旧的 cnt[number]
++freq[++cnt[number]]; // 添加一个新的 cnt[number]
}
void deleteOne(int number) {
if (!cnt[number]) return; // 不删除任何内容
--freq[cnt[number]]; // 去掉一个旧的 cnt[number]
++freq[--cnt[number]]; // 添加一个新的 cnt[number]
}
bool hasFrequency(int frequency) {
return freq[frequency]; // 至少有一个 number 的出现次数恰好为 frequency
}
};
/**
* Your FrequencyTracker object will be instantiated and called as such:
* FrequencyTracker* obj = new FrequencyTracker();
* obj->add(number);
* obj->deleteOne(number);
* bool param_3 = obj->hasFrequency(frequency);
*/
javascript 解法, 执行用时: 481 ms, 内存消耗: 107.7 MB, 提交时间: 2024-03-21 09:20:55
class FrequencyTracker {
constructor() {
this.cnt = new Map(); // number 的出现次数
this.freq = new Map(); // number 的出现次数的出现次数
}
add(number, delta = 1) {
let c = this.cnt.get(number) ?? 0;
this.freq.set(c, (this.freq.get(c) ?? 0) - 1); // 去掉一个旧的 cnt[number]
c += delta;
this.cnt.set(number, c);
this.freq.set(c, (this.freq.get(c) ?? 0) + 1); // 添加一个新的 cnt[number]
}
deleteOne(number) {
if ((this.cnt.get(number) ?? 0) > 0) {
this.add(number, -1);
}
}
hasFrequency(frequency) {
return (this.freq.get(frequency) ?? 0) > 0; // 至少有一个 number 的出现次数恰好为 frequency
}
}
/**
* Your FrequencyTracker object will be instantiated and called as such:
* var obj = new FrequencyTracker()
* obj.add(number)
* obj.deleteOne(number)
* var param_3 = obj.hasFrequency(frequency)
*/
rust 解法, 执行用时: 83 ms, 内存消耗: 84.1 MB, 提交时间: 2024-03-21 09:20:19
use std::collections::HashMap;
struct FrequencyTracker {
cnt: HashMap<i32, i32>, // number 的出现次数
freq: HashMap<i32, i32>, // number 的出现次数的出现次数
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl FrequencyTracker {
fn new() -> Self {
Self { cnt: HashMap::new(), freq: HashMap::new() }
}
fn update(&mut self, number: i32, delta: i32) {
let c = self.cnt.entry(number).or_insert(0);
*self.freq.entry(*c).or_insert(0) -= 1; // 去掉一个旧的 cnt[number]
*c += delta;
*self.freq.entry(*c).or_insert(0) += 1; // 添加一个新的 cnt[number]
}
fn add(&mut self, number: i32) {
self.update(number, 1);
}
fn delete_one(&mut self, number: i32) {
if *self.cnt.get(&number).unwrap_or(&0) > 0 {
self.update(number, -1);
}
}
fn has_frequency(&self, frequency: i32) -> bool {
*self.freq.get(&frequency).unwrap_or(&0) > 0 // 至少有一个 number 的出现次数恰好为 frequency
}
}
/**
* Your FrequencyTracker object will be instantiated and called as such:
* let obj = FrequencyTracker::new();
* obj.add(number);
* obj.delete_one(number);
* let ret_3: bool = obj.has_frequency(frequency);
*/
php 解法, 执行用时: 398 ms, 内存消耗: 96.4 MB, 提交时间: 2024-03-21 09:19:29
class FrequencyTracker {
private $cnt;
private $freq;
/**
*/
function __construct() {
$this->cnt = []; # 每个数的出现次数
$this->freq = []; # 出现次数的出现次数
}
/**
* @param Integer $number
* @return NULL
*/
function add($number) {
$this->freq[$this->cnt[$number]] -= 1; # 直接减，因为下面询问的不会涉及到 frequency=0
$this->cnt[$number] += 1;
$this->freq[$this->cnt[$number]] += 1;
}
/**
* @param Integer $number
* @return NULL
*/
function deleteOne($number) {
if ( $this->cnt[$number] == 0 )
return; # 不删除任何内容
$this->freq[$this->cnt[$number]] -= 1;
$this->cnt[$number] -= 1;
$this->freq[$this->cnt[$number]] += 1;
}
/**
* @param Integer $frequency
* @return Boolean
*/
function hasFrequency($frequency) {
return $this->freq[$frequency] > 0;
}
}
golang 解法, 执行用时: 320 ms, 内存消耗: 84.9 MB, 提交时间: 2023-05-08 09:52:27
type FrequencyTracker struct {
cnt map[int]int // 每个数的出现次数
freq map[int]int // 出现次数的出现次数
}
func Constructor() (_ FrequencyTracker) {
return FrequencyTracker{map[int]int{}, map[int]int{}}
}
func (f FrequencyTracker) Add(number int) {
f.freq[f.cnt[number]]-- // 直接减，因为下面询问的不会涉及到 frequency=0
f.cnt[number]++
f.freq[f.cnt[number]]++
}
func (f FrequencyTracker) DeleteOne(number int) {
if f.cnt[number] == 0 {
return // 不删除任何内容
}
f.freq[f.cnt[number]]--
f.cnt[number]--
f.freq[f.cnt[number]]++
}
func (f FrequencyTracker) HasFrequency(frequency int) bool {
return f.freq[frequency] > 0
}
/**
* Your FrequencyTracker object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(number);
* obj.DeleteOne(number);
* param_3 := obj.HasFrequency(frequency);
*/
java 解法, 执行用时: 38 ms, 内存消耗: 107.7 MB, 提交时间: 2023-05-08 09:52:15
class FrequencyTracker {
private Map<Integer, Integer> cnt = new HashMap<>(); // 每个数的出现次数
private Map<Integer, Integer> freq = new HashMap<>(); // 出现次数的出现次数
public FrequencyTracker() {}
public void add(int number) {
// 直接减，因为下面询问的不会涉及到 frequency=0
freq.merge(cnt.getOrDefault(number, 0), -1, Integer::sum);
int c = cnt.merge(number, 1, Integer::sum);
freq.merge(c, 1, Integer::sum);
}
public void deleteOne(int number) {
if (cnt.getOrDefault(number, 0) == 0) return; // 不删除任何内容
freq.merge(cnt.get(number), -1, Integer::sum);
int c = cnt.merge(number, -1, Integer::sum);
freq.merge(c, 1, Integer::sum);
}
public boolean hasFrequency(int frequency) {
return freq.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);
*/
python3 解法, 执行用时: 500 ms, 内存消耗: 77.8 MB, 提交时间: 2023-05-08 09:51:56
class FrequencyTracker:
def __init__(self):
self.cnt = Counter() # 每个数的出现次数
self.freq = Counter() # 出现次数的出现次数
def add(self, number: int) -> None:
self.freq[self.cnt[number]] -= 1 # 直接减，因为下面询问的不会涉及到 frequency=0
self.cnt[number] += 1
self.freq[self.cnt[number]] += 1
def deleteOne(self, number: int) -> None:
if self.cnt[number] == 0: return # 不删除任何内容
self.freq[self.cnt[number]] -= 1
self.cnt[number] -= 1
self.freq[self.cnt[number]] += 1
def hasFrequency(self, frequency: int) -> bool:
return self.freq[frequency] > 0
# Your FrequencyTracker object will be instantiated and called as such:
# obj = FrequencyTracker()
# obj.add(number)
# obj.deleteOne(number)
# param_3 = obj.hasFrequency(frequency)