算法练习——3005. 最大频率元素计数

题目描述：

给你一个由?正整数?组成的数组?nums?。

返回数组?nums?中所有具有?最大?频率的元素的?总频率?。

元素的?频率?是指该元素在数组中出现的次数。

示例 1：

输入：nums = [1,2,2,3,1,4]
输出：4
解释：元素 1 和 2 的频率为 2 ，是数组中的最大频率。
因此具有最大频率的元素在数组中的数量是 4 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：5
解释：数组中的所有元素的频率都为 1 ，是最大频率。
因此具有最大频率的元素在数组中的数量是 5 。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

通过代码：?

class Solution {
    public int maxFrequencyElements(int[] nums) {
        int maxFrequency = -1;
        List<Integer> maxNumList = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.getOrDefault(num, 0) > maxFrequency){
                maxFrequency = map.getOrDefault(num, 0);
                maxNumList.clear();
                maxNumList.add(num);
            }else if (map.getOrDefault(num, 0) == maxFrequency){
                maxNumList.add(num);
            }
        }
        return maxNumList.size() * maxFrequency;
    }
}

代码解析：

代码中首先声明了一些变量，作用如下：

maxFrequency——记录最大频率，整型变量；

maxNumList——记录数组?nums中频率最大的元素，整型数组；

map——记录数组?nums中的元素在nums中出现的频次，哈希表。

接着遍历数组nums，遍历的过程中，不断的更新map中的值，并在当前字母更新map值后与maxFrequency进行比较：

• 如果当前字母存储的哈希值此时大于当前存储的最大频率，那么将maxFrequency存储为当前字母的频率值，并清理当前存储的maxNumList中的内容；再将当前字母放入maxNumList中。
• 如果当前字母存储的哈希值此时等于当前存储的最大频率，那么将当前字母放入maxNumList中。

则数组?nums?中所有具有?最大?频率的元素的?总频率 即为：

maxNumList数组的长度 *?maxFrequency频率

复杂度分析：

时间复杂度：O(n)? ? ? ? ????????????????????????????????空间复杂度：O(n)?

优化思路：

由于题目只要求计算nums中所有具有?最大?频率的元素的?总频率，所以可将题目中maxNumList仅存储一个整型变量maxNumCount用来计数，对应的

maxNumList.clear()；?????????????可改为????????maxNumCount = 0；

maxNumList.add(num);? ? ? ? ? 可改为????????maxNumCount++；

最终的计算结果为：? ? ??

maxNumCount *?maxFrequency

这样可以优化一定的内存消耗！

欢迎您留言评价讨论！