<分区>
我有大量数据(>10000000)，类型为 int，每个新项目我都想计算中位数(所以我将有 >1000000 个中位数)。我应该维护一个排序列表并按顺序将项目插入此列表，然后每次计算中位数，还是应该每次插入然后对列表进行排序。
此外，std::vector 是否适合此数据结构？或者另一种数据结构会提供更好的复杂性
注意:我不能使用 std::set 因为也可能有重复如果使用 std::multiset 查找中位数会增加复杂性，因为我将从从开始到中间得到它的值(value)。
最佳答案
我会使用 std::multiset，因为它可以处理重复项并自动维护排序顺序。我会一个一个地插入数字，维护一个指向中位数的迭代器(向前或向后步进取决于新元素是大于还是小于中位数)。
请注意，如果这变得太大而不能很好地保存在内存中，您可以将大量最高和最低元素打包到文件中；中位数不太可能移动那么远，如果移动了那么远，您可以打开包装并重新包装。
关于c++ - 计算大量数据的中位数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31375283/