基本陣列題 統計最多出現次數的偶數 Leetcode #2404 Most Frequent Even Element

這題的題目在這裡:

題目敘述

題目會給定我們一個陣列，要求我們找出裡面統計最多出現次數的偶數 。

測試範例

Example 1:

Input: nums = [0,1,2,2,4,4,1]
Output: 2
Explanation:
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.
2出現兩次
4出現兩次
2比4小，選2 (平手時的規則)​

Example 2:

Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: 4 is the even element appears the most.
4出現4次
2出現1次

Example 3:

Input: nums = [29,47,21,41,13,37,25,7]
Output: -1
Explanation: There is no even element.
沒有偶數​

約束條件

Constraints:

• 1 <= nums.length <= 2000
• 0 <= nums[i] <= 105

演算法

先過濾掉奇數部分，只留下偶數。

再用字典統計出現次數，次數最多的偶數留下來。

假如有兩個偶數出現的次數一樣多，取最數字比較小的那個最為答案。

程式碼

class Solution:
　def mostFrequentEven(self, nums: List[int]) -> int:
　　target = -1
　　frequency = Counter()
　　
　　for number in nums:

　　　# skip odd numbers
　　　if number % 2: continue  

　　　frequency[number] += 1
　　　
　　　# update even element with largest frequency
　　　if frequency[number] > frequency[target] or frequency[number] == frequency[target] and number < target:
　　　　target = number  

　　return target

複雜度分析

時間複雜度:

O( n ) 從左到右，每個數字複掃描一次。

空間複雜度:

O( n ) 建立了一個字典，最大可能的佔用空間和陣列長度一樣長O(n)

關鍵知識點

計數類Counting的應用題，想到比較適合的對應底層支持資料結構是字典、雜湊映射表(dictionary, hash map)

Reference:

[1] LeetCode - The World's Leading Online Programming Learning Platform