计算模式的算法

一尘不染

计算模式的算法

algorithm

我正在尝试设计一种函数形式的算法，该函数接受两个参数，即数组和数组的大小。我希望它返回数组的模式，如果有多个模式，请返回其平均值。我的策略是采用阵列并首先对其进行排序。然后计算一个数字的所有出现次数。当该数字出现时，将一个加到计数器上并将该计数存储在数组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;
    }

}

阅读 200

2020-07-28

共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的答案相比，如果数字中有很多重复，这应该会更快，但是如果数字 大多是 唯一的，他的速度可能会更快。

2020-07-28