算法,求1亿个数的中位数解决方法
算法,求1亿个数的中位数
内存只能容纳100W个数,现在有1亿数,混序,然后求这一亿个数的中位数,中位数(就是一个有序数组的中间数字,数组长度为偶数就是两个,奇数则只有一个)
我想了半天最后只想出一个超没效率的方法,所以请各位大虾能够指点一下.
------解决方案--------------------
你什么内存啊，
1亿个数字也就几百MB而已啊。。。
------解决方案--------------------
内存只能容纳100W个数 这个只能算是个限制条件吧`~
------解决方案--------------------
是不是说要先排序，然后找出中间的那个数或中间的那两个数
数字有1亿个，太多了，排序算法或许可以有归并算法
学了太久了，也不知道是不是，回去想想后再来看看
------解决方案--------------------
如果100w个数是个规定，想法应该类似文件的对路归并排序了。。
------解决方案--------------------
外排，然后取第五千万和五千万零一的数。
内存只能容纳100W个数,现在有1亿数,混序,然后求这一亿个数的中位数,中位数(就是一个有序数组的中间数字,数组长度为偶数就是两个,奇数则只有一个)
我想了半天最后只想出一个超没效率的方法,所以请各位大虾能够指点一下.
------解决方案--------------------
你什么内存啊，
1亿个数字也就几百MB而已啊。。。
------解决方案--------------------
内存只能容纳100W个数 这个只能算是个限制条件吧`~
------解决方案--------------------
是不是说要先排序，然后找出中间的那个数或中间的那两个数
数字有1亿个，太多了，排序算法或许可以有归并算法
学了太久了，也不知道是不是，回去想想后再来看看
------解决方案--------------------
如果100w个数是个规定，想法应该类似文件的对路归并排序了。。
------解决方案--------------------
外排，然后取第五千万和五千万零一的数。