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 regalia（可以这么说）：

#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

Jerry 已经解释了它是如何工作的。我只想在 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 这将成为一个两行但可能会因整数溢出而失败：

#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

按升序对它们进行排序并添加最后五个数字

Answer 4

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

最后，对数组求和并除以 5。