c++ - 最大出现次数

Question

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

Answer 1

Here is one way of doing it in 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;
}

You could use the above function this way:

#include <iostream>

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

Here is a live example.

With a minor modification, the above function can be generalized to work with any container (not just 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;
}

Thanks to template type deduction, you would call the above function template exactly like you called the original one.

Here is a live example.

Also, for even better performance, you may consider using C++11's std::unordered_map rather than std::map. std::unordered_map gives you amortized O(1) complexity for insertion and lookup. I'll leave its usage in the above examples up to you as an exercise.

Answer 2

你可以O(n log n)在 C++ 中解决这个问题。

首先使用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)。