最大频率元素计数

标签: 数组 哈希表 计数

难度: Easy

给你一个由 正整数 组成的数组 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

Submission

运行时间: 22 ms

内存: 16.0 MB

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        ds = Counter(nums)
        maxN = max(x for x in ds.values())
        ans = 0
        for k,v in ds.items():
            if v == maxN:
                ans += v
        return ans

Explain

本题解首先使用了Counter来统计数组nums中每个元素的频率,存储在字典ds中。接着,通过遍历ds的值找到最大频率maxN。然后,再次遍历ds,统计所有频率等于maxN的元素的频率总和,这一总和即为所有具有最大频率的元素在数组中出现的次数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        ds = Counter(nums)  # 使用Counter统计每个元素的频率
        maxN = max(x for x in ds.values())  # 找到最大的频率值maxN
        ans = 0
        for k,v in ds.items():  # 遍历字典,统计所有频率为maxN的元素的频率总和
            if v == maxN:
                ans += v
        return ans  # 返回所有具有最大频率的元素的总频率

Explore

Counter对象会为数组中每个元素计算其出现的次数,并以字典形式返回。通过从这个字典中找到最大的值,我们可以确保这个最大值代表的是数组中出现频率最高的元素的频率。因为Counter确实计算了所有元素的频率,所以通过检查所有这些频率值,我们可以准确地找到最大频率。

使用生成器表达式可以直接在遍历Counter字典的值时计算最大值,这样做可以节省内存,因为生成器表达式不需要先将所有值存储在一个临时列表中。直接使用max函数同样有效,但使用生成器表达式是一种更优雅且内存效率更高的方式。

可以在第一次遍历字典时同时计算最大频率和对应的元素总数。即在构建Counter对象后,遍历每个元素的频率,同时更新最大频率和对应频率的元素的累积总数。这样可以将两次遍历合并为一次,提高算法效率。

当数组中每个元素都是唯一的时候,Counter对象中每个元素的频率都是1,算法依然能够正确地返回所有元素的总频率,即数组的长度。当所有元素都相同的时候,Counter只会有一个键值对,其频率等于数组的长度,算法可以立即确定这是最大频率并返回。在这两种边界情况下,算法都能以高效的方式执行,不会出现性能下降。