100個の数字からなる配列の5つの最高値の合計を求める

Question

配列内に100個の数字があり、それらの中で上位5個の数字の平均を見つける必要があります。

同様に、それらの中でも上位5つの数字の平均が同じです。どのように私はそれをやって行くことができますか？

Answer 1

使用ホーアの選択アルゴリズムを追加し、その後、トップパーティション（と除算を追加その平均サイズを得るためのサイズによって）。

これは、パーティション化ではなく明示的なソート方法よりもやや高速です - パーティション化は（O(N)）で、ソートはO(N log(N))です。

編集：C++では、実際のコード（要求の一部が自分でタスクを完全に実行すること以外は何もしません）の場合は、std::nth_elementを使用して入力をトップ5とそれ以外のすべてに分割できます。

EDIT2：ここ@Nilsを補完する別の迅速なデモのだが、この1つは完全な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

昇順でソートしてと（あなたは計算の複雑さの絶対的に特定する必要がある場合、または中央値の中央値）最後の5つの数字

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で割ります。