获得std :: set的中间(中位数)的有效方法?

>不是 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的中间(中位数)的有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！