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可解。
楼主的问题就是等价于如何实现找中值的问题,所以你的回答是没有任何意义的,至于现成算法当然可以用。
。。。
算了,不说啥了。