if it is a problem for kids, then sufficient to use a priority queue with capacity set at 500: just dump the content of the queue at the end of the run and then we will have the answer. otherwise, think about self-balancing binary search tree // for interview like setting splay tree, or treaps // for work scenario
请问如何分割成两个部分，让这两部分个数相同，其中一个部分是很大的数，另一个部分是很小的数。
不用排完，以中值为标准，比一遍分开两部分就可以了。
多谢。我最后决定采用你这个简单的方法。
采用mean或者median 有时候，会发生一个集合很多数，一个集合很少的数。
比如：1， 100， 200,100,101,205
有一个集合只有1，这样一个元素。
注意reroot的时候，我说的简单了，要稍微麻烦一点，自己小心看看。应该是把右边subtree最左端的leaf和下面的subtree移上来，把上面压下去。不过这都是标准程序，应该能找到package。
这个应该是最优解，而且median of median结束时左右两边已经是in place的，不用run第二遍
otherwise, think about
self-balancing binary search tree // for interview like setting splay tree, or treaps // for work scenario
Yes, you are right. No need for the last run
找出中值这也叫答案？你还不如说找到中间，把两边一分就分开了。
Balanced tree
冒昧的猜测一句，你不是学计算机课班出身的吧？
median of median是一个很经典算法，非常的基础。
复杂度O（n). Linear可解。
楼主的问题就是等价于如何实现找中值的问题，所以你的回答是没有任何意义的，至于现成算法当然可以用。
。。。
算了，不说啥了。