如何高效地获取std::set的中间值（中位数）？

这个建议非常巧妙，但如果存在重复项，则会失败

根据你插入/删除项目与查找中间/中位数的频率，可能比显而易见的解决方案更有效的解决方案是保持对中间元素的持久迭代器，并在插入/删除项目时更新它。需要处理一堆边缘情况（奇数 vs 偶数数量的项目，删除中间项目，空集等），但基本想法是当您插入小于当前中间项的项目时，您的中间迭代器可能需要递减，而如果您插入大于当前中间项的项，则需要递增。删除操作则相反。

建议

第一个建议是使用std::multiset而不是std::set，这样可以很好地处理重复项

我的建议是使用两个multiset来跟踪小部分和大部分并平衡它们之间的大小

算法

1. 保持集合平衡，使size_of_small == size_of_big或size_of_small + 1 == size_of_bigvoid balance(multiset &small, multiset &big)

{

while (true)

{

int ssmall = small.size();

int sbig = big.size();

if (ssmall == sbig || ssmall + 1 == sbig) break; // OK

if (ssmall < sbig)

{

// big to small

auto v = big.begin();

small.emplace(*v);

big.erase(v);

}

else

{

// small to big

auto v = small.end();

--v;

big.emplace(*v);

small.erase(v);

}

}

}

2. 如果集合是平衡的，中位数总是大集合的第一个项目auto medium = big.begin();

cout << *medium << endl;

3. 添加新项目时要谨慎auto v = big.begin();

if (v != big.end() && new_item > *v)

big.emplace(new_item );

else

small.emplace(new_item );

balance(small, big);

复杂性解释

查找中位数的时间复杂度为 O(1)。

添加一个新项的时间复杂度为 O(log n)。

虽然你需要搜索2个集合，但仍可以在 O(log n) 的时间复杂度内搜索到一个项目。