提取最小值和最大值的最有效方法是什么

Question

给定一个向量

到目前为止，我想出的最好的主意是一个接一个地调用std：：nth_element 3次。但这仍然需要3N比较，对吧？有没有办法重用在以前的迭代中完成的部分排序？




Answer 1

匿名用户

另一个选项是为< code>std::nth_element指定一个自定义比较，它捕获最小值和最大值。它可能会做更多的比较和分支，所以在某些特定的硬件上可能会慢一些，这可能取决于你的数据被缓存了多少等等。，所以——一如既往——如果您有理由关心的话，可以进行基准测试，但是对于非空的< code > vector < code > a 来说，技术是这样的:

int min = a[0], max = a[0];
std::nth_element(a.begin(), a.begin() + n, a.end(),
    [&](int lhs, int rhs) {
        min = std::min(min, std::min(lhs, rhs));
        max = std::max(max, std::max(lhs, rhs));
        return lhs < rhs;
    });

不管它值多少钱，在我的（~10yo i5-660）HTPC上，使用GCC 7.4，100万随机ints介于0和1000之间，nth_。

Answer 2

使用＜code＞std：：n_。

如果您需要它比这更快，那么请根据std：：nth_element滚动您自己的版本。