在数组中找到大多数occurence元素 [英] find most occurence element in array

问题描述

这里是一个简单的程序来查找最常出现在数组中的元素：

Here is simple program to find the element which occurs most often in an array:

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    int a[] = {1,2,3,4,4,4,5};
    int n = sizeof(a) / sizeof(int);
    int max = 0;
    int result = 0;
    int *b = new int[n];
    for (int i = 0;  i < n;  i++) {
        b[a[i]] = (b[a[i]] || 0) + 1;
        if (b[a[i]] > max) {
            max = b[a[i]];
            result = a[i];
        }
    }
    cout << result << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

但它不工作;它打印 1 。为什么？

But it doesn't work; it prints 1. Why?

推荐答案

因为你包括向量，为什么不替换 int * b = new int [ n]; with std :: vector< int> b（n）？这也照顾释放记忆，你忘了 delete [] b 。

Since you are including vector anway, why not replace int *b=new int [n]; with std::vector<int> b(n)? This also takes care of releasing the memory, you forgot to delete[] b.

但正如其他人所说，如果数组包含大于n的元素，您的解决方案将中断。一个更好的方法可能是使用映射到int来计数元素。这样，你也可以计算不能用作数组索引的元素，例如字符串。

But as others have mentioned, your solution will break if the array contains elements larger than n. A better approach might be to count the elements with a mapping to int. That way, you can also count elements that cannot be used as an array index, for example strings.

也没有理由限制数组。这里是一个通用的解决方案，适用于任何小于可比较的元素类型的任何容器：

There is also no reason to limit ourselves to arrays. Here is a generic solution that works with any container of any less-than comparable element type:

#include <algorithm>
#include <iterator>
#include <map>

struct by_second
{
    template <typename Pair>
    bool operator()(const Pair& a, const Pair& b)
    {
        return a.second < b.second;
    }
};


template <typename Fwd>
typename std::map<typename std::iterator_traits<Fwd>::value_type, int>::value_type
most_frequent_element(Fwd begin, Fwd end)
{
    std::map<typename std::iterator_traits<Fwd>::value_type, int> count;

    for (Fwd it = begin; it != end; ++it)
        ++count[*it];

    return *std::max_element(count.begin(), count.end(), by_second());
}

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> test {1, 2, 3, 4, 4, 4, 5};
    std::pair<int, int> x = most_frequent_element(test.begin(), test.end());
    std::cout << x.first << " occured " << x.second << " times";
}

这篇关于在数组中找到大多数occurence元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！