Daily LeetCode – day0020 1224. Maximum Equal Frequency

// 1224. Maximum Equal Frequency
class Solution {
    public int maxEqualFreq(int[] nums) {
        HashMap<Integer, Integer> numberFrequencyMap = new HashMap<>();
        HashMap<Integer, Integer> frequencyFrequencyMap = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            int frequency = numberFrequencyMap.getOrDefault(nums[i], 0) + 1;
            numberFrequencyMap.put(nums[i], frequency);
            if (frequency > 1) {
                if (frequencyFrequencyMap.get(frequency - 1) == 1) {
                    frequencyFrequencyMap.remove(frequency - 1);
                } else {
                    frequencyFrequencyMap.put(frequency - 1, frequencyFrequencyMap.get(frequency - 1) - 1);
                }
            }
            frequencyFrequencyMap.put(frequency, frequencyFrequencyMap.getOrDefault(frequency, 0) + 1);
            if (possible(frequencyFrequencyMap)) ans = i + 1;
        }
        return ans;
    }

    private boolean possible(HashMap<Integer, Integer> ffm) {
        if (ffm.size() > 2) {
            return false;
        } else if (ffm.size() == 2) {
            Iterator<Map.Entry<Integer, Integer>> iterator = ffm.entrySet().iterator();
            Map.Entry<Integer, Integer> e1 = iterator.next();
            Map.Entry<Integer, Integer> e2 = iterator.next();
            if (e1.getKey() - e2.getKey() == 1 && e1.getValue() == 1) return true;
            if (e2.getKey() - e1.getKey() == 1 && e2.getValue() == 1) return true;
            if (e1.getKey() == 1 && e1.getValue() == 1) return true;
            if (e2.getKey() == 1 && e2.getValue() == 1) return true;
            return false;
        } else {
            Iterator<Map.Entry<Integer, Integer>> iterator = ffm.entrySet().iterator();
            Map.Entry<Integer, Integer> e1 = iterator.next();
            return e1.getKey() == 1 || e1.getValue() == 1;
        }
    }
}
学习笔记:
这道题是一道HashMap的题,情况特别多特别难。
由于情况非常复杂,我们应该自顶向下编程,先写好主函数,然后再把最关键的判定函数写出来。
主函数用了两次HashMap的getOrDefault函数,让代码显得优雅和精简。

当频率大于两种时,肯定不符合。

当频率达到两种时,会有两个情况符合:
11111222233334444,多一个的频率只有1次。
1222233334444,频率为1的只有1次。

当频率只有一种时,会有两个情况符合:
11111111111111,这个频率只出现了1次。
12345678,频率为1。

这里为了拿到HashMap的唯一Entry或唯二Entry属实麻烦,用上了迭代器iterator。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。