多数元素

题目

多数元素

思路分析一

.第一个想法，暴力遍历，然后会发现容易超时，那么更进一步想：哈希表

• 使用哈希表存储每个数出现的次数，即使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数
• 加入后，遍历所有键值对，返回最大的键
• 也可以在遍历的同时寻找最大键

代码一

#include <iostream>  
#include <vector>  
#include<map>
using namespace std;

int majorityElement(vector<int>& nums) 
{
    map<int, int>count;
    int x = 0, votes = 0; //初始化候选多数元素x和票数votes
    for (int num : nums) 
    {
        ++count[num];
        if (count[num] > votes)
        {
            x = num;
            votes = count[num];
        }
    }
    return x;
}

int main() 
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> nums[i];
    }
    cout << majorityElement(nums);
    return 0;
}

　　放在力扣的答案为：

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        map<int, int>count;
        int x = 0, votes = 0; //初始化候选多数元素x和票数votes
        for (int num : nums)
        {
            ++count[num];
            if (count[num] > votes)
            {
                x = num;
                votes = count[num];
            }
        }
        return x;
    }
};

思路分析二

学习数学的时候有一个小知识点：经过单调排序后，下标为数组一半的元素（下标从 0 开始）一定是众数。

代码二

#include <iostream>  
#include <vector>  
#include<algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end());
    cout << nums[nums.size() / 2];
    return 0;
}

　　放在力扣的答案：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};