计算模式的算法

Question

我试图以函数的形式设计一个算法,该函数接受两个参数,一个数组和数组的大小.我希望它返回数组的模式,如果有多种模式,则返回它们的平均值.我的策略是采用数组并首先对其进行排序.然后计算所有出现的数字.当该数字发生时,添加一个计数器并将该计数存储在数组m中.所以m保持所有计数,另一个数组q保持我们比较的最后一个值.

例如:我的名单是{1, 1, 1, 1, 2, 2, 2} 我的m[0] = 4 q[0] = 1 and then m[1] = 3 and q[1] = 2.

所以模式是 q[0] = 1;

不幸的是,到目前为止我没有成功.希望有人可以提供帮助.

float mode(int x[],int n)
{
    //Copy array and sort it
    int y[n], temp, k = 0, counter = 0, m[n], q[n];

    for(int i = 0; i < n; i++)
        y[i] = x[i];

    for(int pass = 0; pass < n - 1; pass++)
        for(int pos = 0; pos < n; pos++)
            if(y[pass] > y[pos]) {
                temp = y[pass];
                y[pass] = y[pos];
                y[pos] = temp;
            }

    for(int i = 0; i < n;){
        for(int j = 0; j < n; j++){
            while(y[i] == y[j]) {
                counter++;
                i++;
            }
        }
        m[k] = counter;
        q[k] = y[i];
        i--; //i should be 1 less since it is referring to an array subscript
        k++;
        counter = 0;
    }

}

Answer 1

即使你已经有了一些好的答案,我决定发布另一个.我不确定它真的会增加很多新的东西,但我不确定它也不会.如果不出意外,我很确定它使用的标准标题比任何其他答案都要多.:-)

#include <vector>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <iostream>
#include <utility>
#include <functional>
#include <numeric>

int main() {
    std::vector<int> inputs{ 1, 1, 1, 1, 2, 2, 2 };

    std::unordered_map<int, size_t> counts;
    for (int i : inputs)
        ++counts[i];

    std::multimap<size_t, int, std::greater<size_t> > inv;
    for (auto p : counts)
        inv.insert(std::make_pair(p.second, p.first));

    auto e = inv.upper_bound(inv.begin()->first);

    double sum = std::accumulate(inv.begin(),
        e,
        0.0,
        [](double a, std::pair<size_t, int> const &b) {return a + b.second; });

    std::cout << sum / std::distance(inv.begin(), e);
}

与@ Dietmar的答案相比,如果你的数字有很多重复,这应该会更快,但如果这些数字大多是唯一的话,他的可能会更快.