刷题记录帖子

LC. 3005. Count Elements With Maximum Frequency

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.



Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.
Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.


Constraints:

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

我的解法，多变遍历

1. class Solution:
   
2.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
3.         freq = Counter(nums)
   
4.         max_freq = max(freq.values())
   
5. 
   
6.         ans = 0
   
7. 
   
8.         for v in freq:
   
9.             if freq[v] == max_freq:
   
10.                 ans += max_freq
    
11.         
    
12.         return ans
    
13.         

复制代码

优化的同样思路的写法

1. from collections import Counter
   
2. from typing import List
   
3. 
   
4. class Solution:
   
5.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
6.         freq = Counter(nums)
   
7.         max_freq = max(freq.values())
   
8.         
   
9.         # 生成器表达式：遍历所有频次，如果等于最大频次，就累加
   
10.         return sum(f for f in freq.values() if f == max_freq)

复制代码

更加优化的写法， 一次遍历！

核心思路：在遍历数组、累加频率的同时，动态维护当前的 max_freq 和 ans。

如果发现某个数字的频率 大于 当前的 max_freq，说明之前的 ans 都作废了，我们要更新 max_freq，并且把 ans 重置为当前频率。

如果发现某个数字的频率 等于 当前的 max_freq，说明它也是最大频率的候选人，把它的频率累加到 ans 中。

一次遍历代码实现

1. class Solution:
   
2.     def maxFrequencyElements(self, nums: List[int]) -> int:
   
3.         freq = {}
   
4.         max_freq = 0
   
5.         ans = 0
   
6.         
   
7.         for num in nums:
   
8.             # 1. 更新当前数字的频次
   
9.             freq[num] = freq.get(num, 0) + 1
   
10.             cur_freq = freq[num]
    
11.             
    
12.             # 2. 动态维护最大频次和答案
    
13.             if cur_freq > max_freq:
    
14.                 max_freq = cur_freq
    
15.                 ans = cur_freq       # 出现更大的频次，之前的 ans 作废，重新洗牌
    
16.             elif cur_freq == max_freq:
    
17.                 ans += cur_freq      # 和当前最大频次一样，累加到 ans 中
    
18.                
    
19.         return ans

复制代码