c++ - 大小为n的 vector 的m个最小值(c++ 11)

我需要具有nClose元素的 vector 中的n最小值的平均值(第一个零除外)，其中我们知道nClose + 1 < n仅有非负数，并且 vector 至少包含一个零值。此外，nClose将比n小很多，比如说nClose约为10，n约为500。

通常，我将使用min_element来找到最小值，但是这里没有用，因为我需要多个值。目前，我使用以下代码

sort(diff.begin(), diff.end());
double sum = accumulate(diff.begin() + 1, diff.begin() + 1 + nClose, 0);
double avg = sum / nClose;

由于排序是在O(n log n)中进行的，因此我们可以在O(nClose * n)中进行查找，只需找出最小值并将其删除即可，然后重复执行nClose次。知道你们中的一个人如何用c++ 11的算法来实现吗？

最佳答案

您可以为此使用 std::nth_element 。

nth_element(diff.begin(),diff.begin()+nClose+1, diff.end());
double sum = accumulate(diff.begin(), diff.begin() + 1 + nClose, 0);
double avg = sum / nClose;

关于您找到最小值并将其删除的评论:这可能比您当前的解决方案效率更低，因为删除第n个元素需要将第n个位置之后的所有元素向左移动一个位置，从而有效地将算法转化为某种东西像O(nClose * n ^ 2)。

同样，尽管这应该是一个非常有效的解决方案，但我警告您不要过于重视算法复杂性，因为常量实际上可能比Big O表示法中的任何优势都起着更大的作用。