假设我们在C ++中有一个向量/数组，并且我们希望计算这N个元素中哪个元素具有最大的重复出现次数，并输出最高的计数。哪种算法最适合此工作。

例子：

int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}

输出为4，因为2出现了4次。那是2出现的最大次数。

解决方案

对数组进行排序，然后快速通过以对每个数字进行计数。该算法具有O(N * logN)复杂度。

或者，使用数字作为键创建哈希表。在哈希表中为我们键入的每个元素存储一个计数器。我们将能够一口气计算所有元素；但是，算法的复杂性现在取决于急需函数的复杂性。

一点伪代码：

//split string into array firts
strsplit(numbers) //PHP function name to split a string into it's components
i=0
while( i < count(array))
 {
   if(isset(list[array[i]]))
    {
      list[array[i]]['count'] = list + 1
    }
   else
    {
      list[i]['count'] = 1
      list[i]['number']
    }
   i=i+1
 }
usort(list) //usort is a php function that sorts an array by its value not its key, Im assuming that you have something in c++ that does this
print list[0]['number'] //Should contain the most used number

针对空间进行了优化：

然后，快速排序(例如)对项目进行迭代，仅跟踪最大数量的项目。
充其量为O(N log N)。

针对速度进行了优化：

遍历所有元素，并跟踪单独的计数。
该算法将始终为O(n)。

如果我们有RAM并且值不是太大，请使用计数排序。

利用STL的可能的C ++实现可能是：

#include <iostream>
#include <algorithm>
#include <map>

// functor
struct maxoccur
{
    int _M_val;
    int _M_rep;

    maxoccur()
    : _M_val(0),
      _M_rep(0)
    {}

    void operator()(const std::pair<int,int> &e)
    {
        std::cout << "pair: " << e.first << " " << e.second << std::endl;
        if ( _M_rep < e.second ) {
            _M_val = e.first;
            _M_rep = e.second;
        }
    }
};

int
main(int argc, char *argv[])
{
    int a[] = {2,456,34,3456,2,435,2,456,2};
    std::map<int,int> m; 

    // load the map
    for(unsigned int i=0; i< sizeof(a)/sizeof(a[0]); i++) 
        m [a[i]]++;

    // find the max occurence...
    maxoccur ret = std::for_each(m.begin(), m.end(), maxoccur());
    std::cout << "value:" << ret._M_val << " max repetition:" << ret._M_rep <<  std::endl;

    return 0;
}

如果元素的范围比元素的数量大，我将按照其他人所说的那样进行排序和扫描。这是时间n * log n，没有额外的空间(也许是log n额外的)。

计数排序的问题在于，如果值的范围较大，则初始化计数数组要比排序花费更多的时间。

哈希算法(基本上是线性时间的build count [i] = #occurrences(i))非常实用，但从理论上讲并不是严格意义上的O(n)，因为在此过程中可能会发生哈希冲突。

这个问题的一个有趣的特殊情况是多数算法，如果要存在一个元素，则要查找至少存在于n / 2个数组条目中的元素。

这是一个快速的解释，并且更详细地说明了如何在线性时间内执行此操作，而没有任何哈希技巧。

这是我完整的，经过测试的版本，使用的是std :: tr1 :: unordered_map。

我使它大约为O(n)。首先，对n个输入值进行迭代，以插入/更新" unordered_map"中的计数，然后执行" partial_sort_copy"，即O(n)。 2 * O(n)〜= O(n)。

#include <unordered_map>
#include <vector>
#include <algorithm>
#include <iostream>

namespace {
// Only used in most_frequent but can't be a local class because of the member template
struct second_greater {
    // Need to compare two (slightly) different types of pairs
    template <typename PairA, typename PairB>
    bool operator() (const PairA& a, const PairB& b) const
        { return a.second > b.second; }
};
}

template <typename Iter>
std::pair<typename std::iterator_traits<Iter>::value_type, unsigned int>
most_frequent(Iter begin, Iter end)
{
    typedef typename std::iterator_traits<Iter>::value_type value_type;
    typedef std::pair<value_type, unsigned int> result_type;

    std::tr1::unordered_map<value_type, unsigned int> counts;

    for(; begin != end; ++begin)
        // This is safe because new entries in the map are defined to be initialized to 0 for
        // built-in numeric types - no need to initialize them first
        ++ counts[*begin];

    // Only need the top one at this point (could easily expand to top-n)
    std::vector<result_type> top(1);

    std::partial_sort_copy(counts.begin(), counts.end(),
                           top.begin(), top.end(), second_greater());

    return top.front();
}

int main(int argc, char* argv[])
{
    int a[] = { 2, 456, 34, 3456, 2, 435, 2, 456, 2 };

    std::pair<int, unsigned int> m = most_frequent(a, a + (sizeof(a) / sizeof(a[0])));

    std::cout << "most common = " << m.first << " (" << m.second << " instances)" << std::endl;
    assert(m.first == 2);
    assert(m.second == 4);

    return 0;
}

可能在O(n).............但问题是大号。的数组可以取另一个相同大小的数组.........

这里a []是数据数组，我们需要在其中搜索某些数字的最大出现次数。在一个数组中.......

count []具有每个元素的数量.....
注意：我们知道数据的范围将在数组中。
说，例如。该数组中的数据范围为1到100 .....，然后对100个元素的count数组进行跟踪，如果发生的话会使索引值降低1 .....