文章/答案/技术大牛

发布

社区首页 >问答首页 >大小为n的向量的M最小值(c++11)

问大小为n的向量的M最小值(c++11)
EN

Stack Overflow用户

提问于 2015-05-25 12:16:47

回答 1查看 339关注 0票数 3

我需要nClose最小值的平均值(除了第一个零)，在有n元素的向量中，我们知道nClose + 1 < n，只有非负数，并且向量包含至少一个零值。此外，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 )中运行的排序，我们可以在O( nClose *n)中这样做，只需找到最小值并删除它，然后在nClose时间重复此操作。知道你们中的一个怎么用c++11的算法来完成这个任务吗？

c++

algorithm

c++11

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-05-25 12:33:36

为此您可以使用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;

关于查找最小值并删除它的注释:这可能比当前的解决方案效率更低，因为删除nth元素需要将第n个位置之后的所有元素向左移动，从而有效地将算法转换为O(nClose*n^2)。

此外，虽然这应该是一个非常有效的解决方案，但我警告您不要过于强调算法的复杂性，因为常量实际上可能比在Big表示法中的任何优势都要大得多。

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/30438197

复制

相似问题

问大小为n的向量的M最小值(c++11)
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问大小为n的向量的M最小值(c++11)EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问大小为n的向量的M最小值(c++11)
EN