c++ - 在c ++中查找值集合的中位数

Question

可能重复：
计算向量中存储的值的中位数 - C++？

我需要存储一组值，然后能够计算其中值。

c++ 中存储这些值的最佳容器是什么，我如何找到中位数？

（我可能还希望能够删除特定元素，所以我认为 set 可能不是最好的选择......）

Answer 1

缺少任何其他特定要求，您应该默认使用std::vector. 您提到稍后要删除项目；这意味着您可能需要考虑 a std::list。

要找到中位数，您可以使用std::nth_element，要求它以N/2第 -th（或(N-1)/2-th）元素为轴。这在O(N)时间内运行。