資訊

• Question: 3005. Count Element With Maximum Frequency
• From: Leetcode Daily Challenge 2024.03.08
• Difficulty: Easy

---

目錄

• 資訊
• 目錄
• 題目
• 解法
  • 概念
  • 程式碼
• 複雜度
  • 時間複雜度
  • 空間複雜度

---

題目

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

---

解法

概念

以後看到 hash table 跟 counting 就要想到 Python 黑科技，記得以後真的使用前要寫上 import collections 這一行！

這題需要的大概就是紀錄頻率跟比大小，所以如果有能快速幫我找出 maximum 的對應的會比較好實作，這時候就想到了 python 的 collections，因為裡面有個功能是 counter，counter 基本上就是所有計數器該有的功能都先幫你包得好好的，然後用字典讓你做查詢、運算，這次就拿它來使用

• 第 3 行：創一個 counter
• 第 4 - 5 行：用 counter 紀錄元素出現頻率
• 第 6 行：利用 counter.most_common() 功能把出現頻率依照大小排序，回傳一個 list
• 第 7 - 12 行：尋找最大頻率的所有解，把他們加起來
• 第 13 行：回傳答案

程式碼

class Solution:
    def maxFrequencyElements(self, nums: List[int]) -> int:
        c = Counter()
        for e in nums:
            c[str(e)] += 1
        c = c.most_common()
        ans = c[0][1]
        for i in range( 1, len(c), 1 ):
            if c[i][1] != c[0][1]:
                break
            else:
                ans += c[i][1]
        return ans

---

複雜度

時間複雜度

走訪過整條 list 紀錄頻率，所以是

$O(n)$

空間複雜度

創了 counter，後面又為了紀載 cost_common 而多了一個 list，算是

$O(2n)=O(n)$