​LeetCode解法汇总2671. 频率跟踪器

本文主要是介绍​LeetCode解法汇总2671. 频率跟踪器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

https://github.com/September26/java-algorithms

原题链接：. - 力扣（LeetCode）

描述：

请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。

实现 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
• 最多调用 add、deleteOne 和 hasFrequency 共计 2 * 105 次

解题思路：

首先，构建一个对象Model，记录每个数字出现的次数。

然后，构建两个map，第一个numMap，记录出现的数字以及其所对应的model。

第二个frequencyMap，key为出现的次数，value为set记录，代表出现key次的所有model。

add时，首先找到number对应的model，然后次数+1，同时，从frequencyMap的set中找到这个model并删掉。

删除时，也是类似的逻辑。

hasFrequency时，只要判断是否有frequency次的set并且长度>0即可，

代码：

public static class FrequencyTracker {Map<Integer, Model> numMap = new HashMap<>();Map<Integer, Set<Model>> frequencyMap = new HashMap<>();public FrequencyTracker() {}public void add(int number) {Model model = numMap.computeIfAbsent(number, o -> new Model(number));Set<Model> set = frequencyMap.computeIfAbsent(model.frequency, o -> new HashSet<>());set.remove(model);model.frequency++;set = frequencyMap.computeIfAbsent(model.frequency, o -> new HashSet<>());set.add(model);}public void deleteOne(int number) {Model model = numMap.get(number);if (model == null) {return;}Set<Model> set = frequencyMap.computeIfAbsent(model.frequency, o -> new HashSet<>());set.remove(model);model.frequency--;if (model.frequency == 0) {return;}set = frequencyMap.computeIfAbsent(model.frequency, o -> new HashSet<>());set.add(model);}public boolean hasFrequency(int frequency) {return frequencyMap.getOrDefault(frequency, new HashSet<>()).size() > 0;}}static class Model {int key;int frequency = 0;private Model(int key) {this.key = key;}}

这篇关于​LeetCode解法汇总2671. 频率跟踪器的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---