【哈希+map】2404.出现最频繁的偶数元素

【哈希+map】2404. 出现最频繁的偶数元素

Problem: 2404. 出现最频繁的偶数元素

思路

从数组中找出出现次数最多的偶数（如果这样的数有多个，选取较小的那个）

解题方法

原本的想法是使用map+set，map当作哈希表用来计数，set来记录出现次数最多的偶数，(看了大佬的代码)后来优化了只用map，使用int变量res记录出现次数最多的偶数，如果出现次数一样多，且这个数较小，则更新res。

顺便复习了下C++中map和set的用法，这两个都只能通过使用迭代器遍历，但是map可以通过map[key]的方式来访问和赋值，可使用的函数用begin()、end()、find()、clear()等等。

复杂度

• 时间复杂度:

  $O(n)$

• 空间复杂度:

  $O(n)$

Code

原版:

/***
原版
从数组中找出出现次数最多的偶数（如果这样的数有多个，选取较小的那个）
***/
class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        //记录偶数出现的次数,存在mp中
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++){
            int num = nums[i];
            if(num%2==0){
                if(mp.find(num)==mp.end()){//找不到
                    mp[num] = 1;
                }else{
                    mp[num]++;
                }
            }
        }
        //找到mp中的最大值进行插入
        int max =  -1;
        set<int> res;
        for(unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
            if(it->second > max){
                max = it->second;//更新最大值
                res.clear();
                res.insert(it->first);
            }else if(it->second == max){
                res.insert(it->first);
            }
        }
        if(max==-1) return -1;
        else return *(res.begin());
    
    }
};

简单优化后:

/***
简单优化后
从数组中找出出现次数最多的偶数（如果这样的数有多个，选取较小的那个）
***/
class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        //记录偶数出现的次数,存在mp中
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++){
            int num = nums[i];
            if(num%2==0){
                if(mp.find(num)==mp.end()){//找不到
                    mp[num] = 1;
                }else{
                    mp[num]++;
                }
            }
        }
        //找到mp中的最大值进行插入
        int max =  -1;
        int res;
        for(unordered_map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
            if(it->second > max){
                max = it->second;//更新最大值
                res = it->first;
            }else if(it->second == max && res > it->first){
                 res = it->first;
            }
        }
        if(max==-1) return -1;
        else return res;
    
    }
};