c++ - 最大出现次数

标签 c++ count max find-occurrences

<分区>

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

最佳答案

这是在 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::mapstd::unordered_map 为您提供插入和查找的分摊 O(1) 复杂度。我会将其在上述示例中的用法留给您作为练习。

关于c++ - 最大出现次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16792694/

相关文章:

c++ - C++ 已在别处声明时使用未声明的标识符错误

mysql - 选择不同的行,将它们转换为列并计算值

c++ - VexCL:计算 vector 中高于最小值的值的数量

MySQL 使用 Group Bu 返回不正确的值

c++ - 在应用程序和驱动程序之间共享内存

c++ - 在 QLabel 比例尺内制作数据以适应它的高度

c++ - chrono::steady_clock 是否在线程上阻塞?

php - 计算两个日期之间超过 1 小时的天数再加 1 天

sql-server - 如何在 T-SQL 中获取版本号(varchar)列的 MAX 值

R - 如何让 max() 返回变量名而不是变量的内容?