UDN-企业互联网技术人气社区

板块导航

浏览  : 1464
回复  : 4

[BAT题库] 100亿个整数,内存足够,如何找到中位数?内存不足,如何找到中位数?

[复制链接]
顶风尿三丈的头像 楼主
发表于 2015-5-19 11:01:52 | 显示全部楼层 |阅读模式
100亿个整数,内存足够,如何找到中位数?内存不足,如何找到中位数?
发表于 2015-5-19 11:26:54 | 显示全部楼层
内存足够的情况:

可以使用类似quick sort的思想进行,均摊复杂度为O(n),算法思想如下:

随机选取一个元素,将比它小的元素放在它左边,比它大的元素放在右边

如果它恰好在中位数的位置,那么它就是中位数,可以直接返回
  
如果小于它的数超过一半,那么中位数一定在左半边,递归到左边处理

否则,中位数一定在右半边,根据左半边的元素个数计算出中位数是右半边的第几大,然后递归到右半边处理

内存不足的情况:

方法一:分法
思路:一个重要的线索是,这些数都是整数。整数就有范围了,32位系统中就是[-2^32, 2^32- 1],

有了范围我们就可以对这个范围进行二分,然后找有多少个数⼩于Mid,多少数大于mid,然后递归,和基于quicksort思想的第k大方法类似
  
方法二:分桶法
思路:化大为小,把所有数划分到各个小区间,把每个数映射到对应的区间里,对每个区间中数的个数进行计数,数一遍各个区间,看看中位数落在哪个区间,若够小,使用基于内存的算法,否则继续划分
使用道具 举报

回复

发表于 2015-5-22 09:19:23 | 显示全部楼层
常规的方法 有快排,计数排序等
使用道具 举报

回复

发表于 2015-10-13 14:35:41 | 显示全部楼层
不用排序,中位数的特点是一个最多有一半比他大的数据,也做有一半比它小的数。按此原理,对N个数挨个比较大小计数就行了。在比较中,发现任何一个比它大的数据个数大于N/2,或比它小的数据个数大于N/2,则说明次数不符合,继续,直到找到所有同时满足比他大的数和比它小的数的个数都小于或等于N/2。在找出来的数当中,去掉相同的数,把剩下数加和取平均即可。
使用道具 举报

回复

发表于 2015-11-15 19:28:43 | 显示全部楼层
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部