c++ - 从 vector 中提取最小值、最大值和中值的最有效方法是什么

Question

给定一个 vector<T> vec{...}假设 T 是数字类型之一，提取其最小值、最大值和中值的最佳方法是什么？我知道 std::nth_element 以及 std::minmax_element 但是如果一个接一个地调用，它们似乎会做多余的工作。

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

Answer 1

使用 std::nth_element 划分产生中位数，然后在左半部分使用 std::min_element 和 std::max_element在右边。

如果您需要它比这更快，那么根据 std::nth_element 推出您自己的版本。