最大出现次数

Question

我想在数组中找到出现次数最多的元素并知道出现次数。请建议我使用最快的 C++ 代码。（如果有任何帮助，您可以自由使用 STL。）

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);
}

这是一个活生生的例子。

稍加修改，上述函数可以推广到任何容器（不仅仅是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;
}

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

这是一个活生生的例子。

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