c++ - 最大出现次数

Question

<分区>

Answer 1

这是在 C++11 中实现的一种方法:

#include <vector>
#include <map>

int most_frequent_element(std::vector<int> const& v)
{   // Precondition: v is not empty
    std::map<int, int> frequencyMap;
    int maxFrequency = 0;
    int mostFrequentElement = 0;
    for (int x : v)
    {
        int f = ++frequencyMap[x];
        if (f > maxFrequency)
        {
            maxFrequency = f;
            mostFrequentElement = x;
        }
    }

    return mostFrequentElement;
}

你可以这样使用上面的函数:

#include <iostream>

int main()
{
    std::vector<int> v { 1, 3, 5, 6, 6, 2, 3, 4, 3, 5 };
    std::cout << most_frequent_element(v);
}

这是一个live example .

稍作修改后，上述函数可以泛化为适用于任何容器(不仅仅是 std::vector):

template<typename T>
typename T::value_type most_frequent_element(T const& v)
{    // Precondition: v is not empty
    std::map<typename T::value_type, int> frequencyMap;
    int maxFrequency = 0;
    typename T::value_type mostFrequentElement{};
    for (auto&& x : v)
    {
        int f = ++frequencyMap[x];
        if (f > maxFrequency)
        {
            maxFrequency = f;
            mostFrequentElement = x;
        }
    }

    return mostFrequentElement;
}

由于模板类型推导，您可以像调用原始模板一样调用上述函数模板。

这是一个live example .

此外，为了获得更好的性能，您可以考虑使用 C++11 的 std::unordered_map而不是 std::map。 std::unordered_map 为您提供插入和查找的分摊 O(1) 复杂度。我会将其在上述示例中的用法留给您作为练习。