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

Question

我需要 nClose 的平均值具有 n 的 vector 中的最小值(第一个零除外)我们知道的元素 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 的算法实现这一目标吗？

Answer 1

您可以使用 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 表示法中的任何优势发挥更大的作用。