在100个数字的数组中找出5个最高数字的总和

Question

数组中有100个数字,我需要找出其中前5个最高数字的平均值.

同样地,它们中前5个最低数字的平均值也是相同的.我怎么能去做呢？

Answer 1

使用Hoare的选择算法(或中位数的中位数,如果您需要绝对确定计算复杂度),然后添加顶部分区(并除以其大小以获得平均值).

这比显而易见的排序方法更快,而不是分区 - 分区是(O(N)),其中排序是O(N log(N) ).

编辑:在C++中,对于真实代码(即除了家庭作业之外的任何事情,其中​​部分要求是完全依靠自己完成任务),您可以使用std::nth_element将输入分区为前5名和其他所有内容.

编辑2:这是另一个补充@Nils的快速演示,但这个完整的C++ 11版本(可以这么说):

#include <numeric>  
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main(){
    std::vector<int> x {1, 101, 2, 102, 3, 103, 4, 104, 5, 105, 6};

    auto pos = x.end() - 5;

    std::nth_element(x.begin(), pos, x.end());

    auto sum = std::accumulate(pos, x.end(), 0);
    auto mean = sum / std::distance(pos, x.end());

    std::cout << "sum = " << sum << '\n' << "mean = " << mean << "\n";

    return 0;
}