假设我们有一个 C++ 中的向量/数组，我们希望计算这 N 个元素中哪些元素的重复出现次数最多，并输出最高次数。哪种算法最适合这项工作。
例子：
int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}
输出为 4，因为 2 出现了 4 次。这是 2 出现的最大次数。
Abhishek Mishra
问问题
6902 次
9 回答
18
对数组进行排序，然后快速通过以计算每个数字。该算法具有 O(N*logN) 复杂度。
或者，使用数字作为键创建一个哈希表。在哈希表中为您键入的每个元素存储一个计数器。您将能够一次计算所有元素；但是，算法的复杂性现在取决于您的 hasing 函数的复杂性。
于 2008-09-28T09:44:55.953 回答
10
空间优化：
快速排序（例如）然后迭代项目，仅跟踪最大计数。充其量是 O(N log N)。
针对速度进行了优化：
遍历所有元素，跟踪单独的计数。该算法将始终为 O(n)。
于 2008-09-28T10:17:17.123 回答
4
如果您有 RAM 并且您的值不是太大，请使用计数排序。
于 2008-09-28T10:47:35.943 回答
2
使用 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;
}
于 2008-09-28T10:49:35.410 回答
1
一些伪代码：
//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
于 2008-09-28T09:46:02.207 回答
0
如果元素的范围与元素的数量相比很大，我会像其他人所说的那样进行排序和扫描。这是时间 n*log n 并且没有额外的空间（可能是额外的 log n）。
计数排序的问题在于，如果值的范围很大，则初始化计数数组可能比排序花费更多时间。
于 2008-09-28T16:47:37.670 回答
0
这是我完整的、经过测试的版本，使用std::tr1::unordered_map.
我使这个大约为 O(n)。首先，它遍历 n 个输入值以插入/更新 中的计数unordered_map，然后执行partial_sort_copyO(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;
}
于 2008-11-18T05:19:43.937 回答
0
它将在 O(n) 中............但问题是大号。数组可以取另一个相同大小的数组............
对于（我=0；我
马尔=计数[o]；指数=o;
对于（我=0；我
那么输出将是............元素索引发生在最大编号。在这个数组中的次数............
这里 a[] 是我们需要搜索某个数字的最大出现次数的数据数组。在一个数组中......
count[] 具有每个元素的计数........注意：我们已经知道数据范围将在数组中.. 比如说。该数组中的数据范围从 1 到 100 ......然后有 100 个元素的计数数组来跟踪，如果它发生，则将索引值增加一......
于 2009-03-23T04:29:24.783 回答