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

Question

数组中存在100个数字，我需要找出其中前5个最高数字的平均值。

也以同样的方式，其中前5名最低的数字的平均值。我怎么能这样做呢？

Answer 1

使用霍尔的选择算法（或中位数的中位数，如果你需要绝对肯定的计算复杂度），然后添加一个分区（和鸿沟由其大小来获得平均值）。

这比排序而不是分区的显而易见的方法快一点 - 分区是（O(N)）其中排序是O(N log(N))。

编辑：在C++中，对于真正的代码（即除了家庭作业以外的任何部分需求完全由您自己完成任务），您可以使用std::nth_element将输入划分为前5等。

EDIT2：这里还有一个快速的演示，以补充@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; 
} 

Answer 2

排序是按升序和添加最后五个号码

Answer 3

杰里已经解释它是如何工作的。我只是想在C添加实用的代码示例++：

#include <algorithm> 

int averageTop5 (int list[100]) 
{ 
    // move top 5 elements to end of list: 
    std::nth_element (list, list+95, list+100); 

    // get average (with overflow handling) 
    int avg = 0; 
    int rem = 0;  
    for (int i=95; i<100; i++) 
    { 
    avg += list[i]/5; 
    rem += list[i]%5;  
    } 

    return avg + (rem /5); 
} 

随着Jerrys的std ::积聚这就变成了一个两班轮，但可能会失败，整数溢出：

#include <algorithm> 
#include <numeric> 
int averageTop5 (int list[100]) 
{ 
    std::nth_element (list, list+95, list+100); 
    return std::accumulate (list+95, list+100, 0)/5; 
} 

Answer 4

复制前5数字到数组中。确定该数组中最小元素的位置。对于列表中其余部分的95个数字中的每一个，请将其与该最小数字进行比较。如果新号码较大，则将其替换并重新确定短名单中新的最小号码的位置。

最后，由5