C++寻找数组中出现次数最多的元素

Question

我正在寻找一种优雅的方法来确定哪个元素在C++ ptr数组中出现次数最多(模式).

例如,在

{"pear", "apple", "orange", "apple"}

"apple"元素是最常见的元素.

我以前的尝试失败编辑:数组已经排序.

int getMode(int *students,int size)
{
    int mode;
    int count=0, 
    maxCount=0,
    preVal;

    preVal=students[0]; //preVall holds current mode number being compared
    count=1;
    for(int i =0; i<size; i++) //Check each number in the array
    {
        if(students[i]==preVal) //checks if current mode is seen again
        {
            count++; //The amount of times current mode number has been seen.
            if(maxCount<count)  //if the amount of times mode has been seen is more than maxcount
            {
                maxCount=count; //the larger it mode that has been seen is now the maxCount
                mode=students[i]; //The current array item will become the mode
            }else{
                preVal = students[i];
                count = 1;
            }

        }

    }

    return mode; 
}

Answer 1

这个问题有几种可能的解决方案,但首先要提出一些建议:不要使用C风格的数组.使用std::array用于固定的(编译时)大小阵列或std::vector用于在堆阵列(或C++ 14的std::dynarray如果数组的大小是在运行时确定的,而是创建后并不改变).这些容器为您执行内存管理,您不需要单独传递数组大小.除了使用容器之外,更喜欢<algorithm>在合适的地方使用算法.如果您不了解容器和算法,花一些时间熟悉它们,那个时间很快就会得到回报.

所以,这里有一些解决方案草图:

1. 对数组进行排序,然后计算连续值的出现次数.这比跟踪哪些值已经计数以及哪些值没有计算要容易得多.您基本上只需要两个值计数对:一个用于您当前计数的值,一个用于到目前为止的最大计数值.您只需要第五个变量:容器的迭代器.

2. 如果无法对数组进行排序或需要跟踪所有计数,请使用映射将值映射到数组中出现的次数.如果你熟悉std::map,这很简单.最后,搜索最大计数,即最大地图值:

   for (auto i: students) countMap[i]++;
   auto pos = std::max_element(begin(countMap), end(countMap), 
     [](auto lhs, auto rhs){ return lhs.second < rhs.second }); //! see below
   auto maxCount = pos->second;
   

注意:这使用基于C++ 11的范围和C++ 14多态Lambda.显而易见的是,这里可以根据编译器提供的C++ 11/C++ 14支持进行调整.