计算模式算法

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

Answer 2

根据注释，您似乎需要找到最频繁发生的值，如果有多个值发生的次数相同，则需要生成这些值的平均值。看来，这可以很容易地由std::sort()完成，然后是遍历查找值变化的地方，并保持一些运行计数：

template <int Size>
double mode(int const (&x)[Size]) {
    std::vector<int> tmp(x, x + Size);
    std::sort(tmp.begin(), tmp.end());
    int    size(0);  // size of the largest set so far
    int    count(0); // number of largest sets
    double sum(0);    // sum of largest sets
    for (auto it(tmp.begin()); it != tmp.end(); ) {
        auto end(std::upper_bound(it, tmp.end(), *it));
        if (size == std::distance(it, end)) {
            sum += *it;
            ++count;
        }
        else if (size < std::distance(it, end)) {
            size = std::distance(it, end);
            sum = *it;
            count = 1;
        }
        it = end;
    }
    return sum / count;
}

Answer 3

如果您只想计算发生的次数，那么我建议您使用std::map或std::unordered_map。

如果您要将一个计数器映射到每个不同的值，那么使用std::map计数发生的次数是一项简单的任务，因为每个键只能插入一次。要列出列表中的不同数字，只需在地图上迭代即可。

下面是一个如何做到这一点的例子：

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

std::map<int, int> getOccurences(const int arr[], const std::size_t len) {
    std::map<int, int> m;
    for (std::size_t i = 0; i != len; ++i) {
        m[arr[i]]++;
    }
    return m;
}

int main() {
    int list[7]{1, 1, 1, 1, 2, 2, 2};
    auto occurences = getOccurences(list, 7);
    for (auto e : occurences) {
        std::cout << "Number " << e.first << " occurs ";
        std::cout << e.second << " times" << std::endl;
    }
    auto average = std::accumulate(std::begin(list), std::end(list), 0.0) / 7;
    std::cout << "Average is " << average << std::endl;
}

输出：

Number 1 occurs 4 times
Number 2 occurs 3 times
Average is 1.42857