LC 2671. 频率跟踪器，一道中规中矩的数据结构题目，解法平平无奇，却让我学到了「阅读理解」的重要性。

题目

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。

Map+Set版本

思路

  1. 维护每个数据的频率 num2Freq；
  2. 同时维护频率对应数据集合 freq2Nums；
  3. 数据集合使用有序结构 or set，保证读写效率；

思路平平无奇。

实现提交，发现1118个用例，卡在了第1024个上。

百思不得其解，debug两遍也没想出原因。然后在地铁上看了下其他人的解法，发现了卡点：原来是我「阅读理解」出了问题。

我理解错了 deleteOne 的含义，我开始理解的「从数据结构中删除一个 number」是将数据+频率全部删除。

而实际上数据是要降低一次频率！

搞明白错在哪里，代码修正就很快了，如下是修正后的代码。

代码

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

static class SetSolution {

    Map<Integer, Integer> num2Freq;
    Map<Integer, Set<Integer>> freq2Nums;

    public SetSolution() {
        num2Freq = new HashMap<>();
        freq2Nums = new HashMap<>();
    }

    public void add(int number) {
        int freq = num2Freq.getOrDefault(number, 0) + 1;
        num2Freq.put(number, freq);
        freq2Nums.computeIfAbsent(freq, k -> new HashSet<>());
        freq2Nums.get(freq).add(number);
        if (freq2Nums.containsKey(freq - 1)) {
            // 移除较低频率中的当前数据
            freq2Nums.get(freq - 1).remove(number);
        }
    }

    public void deleteOne(int number) {
        if (!num2Freq.containsKey(number)) {
            return;
        }
        int freq = num2Freq.get(number);
        num2Freq.remove(number);
        freq2Nums.get(freq).remove(number);
        if (freq - 1 > 0) {
            // 频率-1的情况
            num2Freq.put(number, freq - 1);
            freq2Nums.computeIfAbsent(freq - 1, k -> new HashSet<>());
            freq2Nums.get(freq - 1).add(number);
        }
    }

    public boolean hasFrequency(int frequency) {
        return freq2Nums.containsKey(frequency) && !freq2Nums.get(frequency).isEmpty();
    }
}

复杂度分析

时间

增、改、查时间复杂度均为O(1)。

空间

使用额外的Map+Set，空间复杂度O(n)。

优化思路，只记录频率下数据量

思路

观察上面解法，同时再读题，会发现数据操作仅存在 add/delete，每一次频率内数据要么多一个少一个，不存在其他信息获取需求，解法1中freq2Nums维护了频率丢应所有原数据，实际上我们仅需要获取频率对应数据量（即频率的数据频率），因此仅维护频率对应数据量即可。

优化后，空间可节省n个。

代码

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

static class CntSolution {
    // 数据元素对应频率
    Map<Integer, Integer> num2Freq;
    // 频率对应数据量；由于数据操作仅存在 add/delete，每一次频率内数据要么多一个少一个，不存在其他信息获取需求，因此仅维护频率对应数据量即可
    Map<Integer, Integer> freq2Cnt;

    public CntSolution() {
        num2Freq = new HashMap<>();
        freq2Cnt = new HashMap<>();
    }

    public void add(int number) {
        int oldFreq = num2Freq.getOrDefault(number, 0);
        int newFreq = oldFreq + 1;

        num2Freq.put(number, newFreq);
        if (oldFreq > 0) {
            freq2Cnt.put(oldFreq, freq2Cnt.get(oldFreq) - 1);
        }
        freq2Cnt.put(newFreq, freq2Cnt.getOrDefault(newFreq, 0) + 1);
    }

    public void deleteOne(int number) {
        if (!num2Freq.containsKey(number)) {
            return;
        }
        int oldFreq = num2Freq.get(number);
        int newFreq = oldFreq - 1;
        if (newFreq == 0) {
            num2Freq.remove(number);
        } else {
            num2Freq.put(number, newFreq);
            freq2Cnt.put(newFreq, freq2Cnt.getOrDefault(newFreq, 0) + 1);
        }
        freq2Cnt.put(oldFreq, freq2Cnt.get(oldFreq) - 1);
    }

    public boolean hasFrequency(int frequency) {
        return freq2Cnt.containsKey(frequency) && freq2Cnt.get(frequency) > 0;
    }
}

复杂度分析

同解法1，实际执行的空间效率更高。

小结

本题中规中矩，很容易产出思路。

但也正像平时与上下游同事沟通，很容易出现理解上的偏差。因此要重视「阅读理解」。