计算众数的算法

Question

我正在尝试设计一个函数算法，接收两个参数，一个是数组，一个是数组的大小。我希望它能返回数组的众数，如果有多个众数，则返回它们的平均值。我的策略是先对数组进行排序，然后计算每个数字出现的次数。当该数字出现时，将计数器加一并将该计数存储在数组m中。因此，m保存了所有计数，另一个数组q保存了我们正在比较的最后一个值。

例如：如果我的列表是{1,1,1,1,2,2,2}，那么我会有m[0]=4，q[0]=1，然后m[1]=3，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;
    }

}

- Amber Roxanna

---

你的函数没有返回任何内容。我不太清楚你所说的“模式”是什么意思，或者函数的结果应该是什么。如果它应该是所有值的平均值，可以使用 return std::accumulate(x, x + n, 0.0) / n;。顺便说一句，C++ 没有可变大小的数组。但是，你可以使用 std::vector<int> y(n);。 - Dietmar Kühl

@DietmarKühl 这个函数还没有完成。通过“mode”，我指的是数组中出现最频繁的值。由于数组的大小是参数n，因此我不使用可变大小的数组。 - Amber Roxanna

你可能想要查看std::map或者std::unordered_map来计算每个数值出现的次数。显然的替代方案是使用Boost bimap。 - Jerry Coffin

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

- Jerry Coffin

---

不错。一个小的改进是将std::accumulate()的第二个参数替换为您已经计算出的e。 - j_random_hacker

@JerryCoffin 这非常令人印象深刻！你能推荐一些关于标准库的书吗？如果我了解了你使用的工具，似乎我可以解决很多问题。问题是我遇到的大多数书籍更像是参考手册而不是教程。我需要一些让我练习这些工具并解释这些工具解决哪类问题以及何时使用它们的东西。如果你有任何想法，请告诉我！ - Amber Roxanna

我想到了三本书：Effective STL（Scott Meyers）、*The C++ Standard Library: A Tutorial and Reference (2nd Edition)*（Nicolai Josuttis）和 *STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library (paperback) (2nd Edition)*（Musser、Saini 和……一个我不记得名字的家伙）。其中，Josuttis 是最注重参考的，而 Meyers 可能是最少的。 - Jerry Coffin

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;
}

- Dietmar Kühl

---

我知道现在想起来很糟糕，但你实际上只使用了上限，所以upper_bound可能更适合。很抱歉我第一次没有仔细阅读。 - Jerry Coffin

@JerryCoffin：您是正确的，我应该自己注意到这一点。话虽如此，在std::sort()之后使用std::find_if()将产生线性算法，而使用std::equal_range()或std::upper_bound()则会导致最坏情况下的O(n log n)行为。当然，std::sort()已经是O(n)，即总体复杂度不会变得更糟。 - Dietmar Kühl

基本问题是你是否期望平均情况下一个个体值重复超过log(N)次。如果重复次数少于log(N)次，我们可以预期使用find_if进行更少的比较。如果重复次数超过log(N)次，我们可以预期使用upper_bound进行更少的比较。 - Jerry Coffin

我认为你可以使upper_bound总体上呈线性增长（或类似的方式）。每次找到一个范围的末尾时，将其后面的下一个位置作为下一次搜索的开始。对于每次搜索，N都会减少，因此在每次搜索之后，您都会对一个更小的数字取对数。 - Jerry Coffin

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

- Felix Glas

Answer 4

这是您代码的可运行版本。m存储数组中的值，q存储它们的计数。最后，它遍历所有值以获取最大计数、众数之和和不同众数的数量。

float mode(int x[],int n)
{
    //Copy array and sort it
    int y[n], temp, j = 0, k = 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;){
        j = i;
        while (y[j] == y[i]) {
          j++;
        }   
        m[k] = y[i];
        q[k] = j - i;
        k++;
        i = j;
    }   

    int max = 0;
    int modes_count = 0;
    int modes_sum = 0;
    for (int i=0; i < k; i++) {
        if (q[i] > max) {
            max = q[i];
            modes_count = 1;
            modes_sum = m[i];
        } else if (q[i] == max) {
            modes_count += 1;
            modes_sum += m[i];
        }   
    }   

    return modes_sum / modes_count;
}

- disatisfieddinosaur