最大相等频率(Leetcode 1224)

题目分析

   又是一个困难题，遇到困难题目，我们先模拟结果。是不是要记录每一个元素出现的次数，然后比较次数是否除了一个数，剩下的均相等？

按照我们的思路，**时间复杂度是O(n^2)**，但是数据量是1e5，因此我们要想一下如何优化。

哈希表

我们如何比较次数除了一个数，剩余的均相等呢？可以用哈希表记录各个次数对应的数字数量，如果哈希表的大小为1，说明所有数字出现的次数都相等。

因此我们要找的结果就是哈希表的尺寸为2，设次数最大为maxFreq。

1. 当maxFreq对应的元素数量为1，记为x，其他元素出现次数均为maxFreq - 1，将x去掉一个，所有的元素都出现maxFreq - 1次。

2. 或者有一个元素出现次数为1，记为x，其他元素出现次数均为maxFreq，将x去掉，所有元素都出现maxFreq次。

3. 注意有一个特殊情况，当maxFreq = 1时，一定是满足条件的。

根据上面的分析，我们可以把比较的过程优化到**O(1)**的复杂度。需要动态保存maxFreq，而且需要动态更新各个次数对应的数字数量freqToCnt。我们要记录各个元素出现的次数，当有元素需要加入前缀时，该次数对应的数字数量-1，该次数+1对应的数字数量+1。

算法同时维护两个哈希表，一个是元素对应出现的次数numberToFreq，一个是次数对应的元素数量freqToCnt。因为是前缀和，所以只需要从索引0一直向后遍历即可，**时间复杂度为O(n)，空间复杂度也是O(n)**。

class Solution {
    public int maxEqualFreq(int[] nums) {
        int maxFreq = 0;
        int res = 0;
        HashMap<Integer, Integer> numberToFreq = new HashMap<>();
        HashMap<Integer, Integer> freqToCnt = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            int freq = numberToFreq.getOrDefault(val, 0);
            numberToFreq.put(val, freq + 1);
            if (freqToCnt.getOrDefault(freq, 0) != 0) {
                freqToCnt.put(freq, freqToCnt.getOrDefault(freq, 1) - 1);
            }
            freqToCnt.put(freq + 1, freqToCnt.getOrDefault(freq + 1, 0) + 1);
            maxFreq = Math.max(maxFreq, freq + 1);
            if (maxFreq == 1
                || (freqToCnt.getOrDefault(maxFreq, 1) == 1 && maxFreq + (maxFreq - 1) * freqToCnt.getOrDefault(maxFreq - 1, 1) == i + 1)
                || (maxFreq * freqToCnt.getOrDefault(maxFreq, 1) == i)) {
                res = i + 1;
            }
        }
        return res;
    }
}

刷题总结

  本题的难点是如何将校验某个前缀是否满足条件优化得到O(1)的复杂度，如何想到使用出现次数映射元素数量的哈希表。如果能想到这个哈希，基本上就能做出来，可能一次难以想得周全，多提交几次，就能考虑到可能出现的三种情况了。