问题描述
std::set 是一个排序树.它提供了 begin 和 end 方法，因此我可以获得最小值和最大值以及 lower_bound 和 upper_bound 用于二进制搜索.但是，如果我想让迭代器指向中间元素(或者如果那里有偶数个元素，则其中之一)怎么办?
std::set is a sorted tree. It provides begin and end methods so I can get minimum and maximum and lower_bound and upper_bound for binary search. But what if I want to get iterator pointing to the middle element (or one of them if there are even number of elements there)?
有没有一种有效的方法(O(log(size)) 而不是 O(size)) 来做到这一点?
Is there an efficient way (O(log(size)) not O(size)) to do that?
{1} => 1
{1,2} => 1 or 2
{1,2,3} => 2
{1,2,3,4} => 2 or 3 (but in the same direction from middle as for {1,2})
{1,312,10000,14000,152333} => 10000
PS:俄语同样的问题.
推荐答案
根据您插入/删除项目与查找中间/中位数的频率，一个可能比显而易见的更有效的解决方案是保持一个持久迭代器中间元素并在您从集合中插入/删除项目时更新它.有一堆需要处理的边缘情况(奇数与偶数项目，删除中间项目，空集等)，但基本思想是当您插入一个小于当前中间项目的项目时，您的中间迭代器可能需要递减，而如果您插入更大的迭代器，则需要递增.删除则相反.
Depending on how often you insert/remove items versus look up the middle/median, a possibly more efficient solution than the obvious one is to keep a persistent iterator to the middle element and update it whenever you insert/delete items from the set. There are a bunch of edge cases which will need handling (odd vs even number of items, removing the middle item, empty set, etc.), but the basic idea would be that when you insert an item that's smaller than the current middle item, your middle iterator may need decrementing, whereas if you insert a larger one, you need to increment. It's the other way around for removals.
在查找时，这当然是 O(1)，但它在每次插入/删除时也有本质上 O(1) 的成本，即 N 次插入后的 O(N)，这需要在足够的时间摊销查找次数，使其比暴力破解更有效.
At lookup time, this is of course O(1), but it also has an essentially O(1) cost at each insertion/deletion, i.e. O(N) after N insertions, which needs to be amortised across a sufficient number of lookups to make it more efficient than brute forcing.
这篇关于获得std :: set中间(中位数)的有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！