在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