最大出现次数

Question

我想查找出现次数最多的元素并知道出现次数。请建议我最快的C++代码，这样做（您可以自由使用STL如果能够帮上什么忙。）

Answer 1

您可以在C++中使用O(n log n)解决此问题。

首先使用O(n log n)排序（堆排序，合并排序，快速排序等）进行排序列表中的元素的数量。如果您不关心算法的复杂性，请使用Bubble Sort对列表进行排序。在这种情况下，算法的复杂性将变为O（n ）。

然后使用以下代码，该代码以O(n)时间从排序列表中查找出现次数最多的元素。

maxfreq=0; 
freq=1; 
for(i=0;i<(MAX-1);i++) 
{ 
    if(list[i]==list[i+1]) 
    { 
    freq++; 
    if(freq > maxfreq) 
    { 
     maxfreq=freq; 
     maxind=i; 
    } 
    } 
    else 
    { 
    freq=1; 
    } 
} 
cout<<"Element "<<list[maxind]<<" occurs "<<maxfreq<<" times in the list"; 

总共花费的时间是O(log n + n)。因此该算法的复杂性为O(log n)。

Answer 2

这里是做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）复杂性。在上面的例子中，我将把它的用法作为练习。