c++ - 100 個の数字の配列で最大の 5 つの数字の合計を求める

Question

配列には 100 個の数字があり、その中で上位 5 つの数字の平均を求める必要があります。

また、同様に、その中で最も低い上位 5 つの数値の平均。どうすればそれを行うことができますか？

Answer 1

Hoare の選択アルゴリズム (または、計算の複雑さを完全に確認する必要がある場合は、中央値の中央値) を使用してから、一番上のパーティションを追加します (そのサイズで割って平均を求めます)。

これは、パーティショニングの代わりにソートする明白な方法よりもいくらか高速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

ジェリーはすでにそれがどのように機能するかを説明しました。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::accumulate を使用すると、これは 2 行になりますが、整数オーバーフローで失敗する可能性があります。

#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 3

最初の 5 つの数字を配列にコピーします。その配列内の最小要素の位置を決定します。リストの残りの 95 個の数字のそれぞれについて、最小の数字と比較します。新しい数値が大きい場合は、それを置き換えて、短いリスト内の新しい最小数値の位置を再決定します。

最後に、配列を合計して 5 で割ります。

Answer 4

それらを昇順に並べ替え、最後の 5 つの数字を追加します