c++ - 最大オカレンス

Question

配列内で出現回数が最大の要素を見つけて、出現回数を知りたいです。そうするための最速の C++ コードを提案してください。

Answer 1

C++11 でそれを行う 1 つの方法を次に示します。

#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++11 の使用を検討してstd::unordered_mapくださいstd::map。std::unordered_map挿入と検索のための償却された O(1) の複雑さを提供します。上記の例での使用法は、演習としてあなたに任せます。

Answer 2

O(n log n)この問題は C++ で解決できます。

最初にO(n log n)並べ替え ( Heap Sort、Merge Sort、Quick Sortなど) を使用して、リスト内の要素の数を並べ替えます。アルゴリズムの複雑さを気にしない場合は、 を使用してリストを並べ替えます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)。