题目标题

2亿个随机生成的无序整数,找出中间大小的值

难度:高级

算法 推荐系统
参考解析

(1)当内存足够时:
采用快排,找到第n大的数。
• 随机选取一个数,将比它小的元素放在它左边,比它大的元素放在右边
• 如果它恰好在中位数的位置,那么它就是中位数,直接返回
• 如果小于它的数超过一半,那么中位数一定在左半边,递归到左边处理(还是第几大)
• 否则中位数一定在右半边,根据左半边的元素个数计算出中位数是右半边的第几大(重新算第几大),然后递归到右半边处理
(2)当内存不足时:
分桶法
把所有数划分到各个小区间,把每个数映射到对应的区间里,对每个区间中数的个数进行计数,数一遍各个区间,看看中位数落在哪个区间,若够小,使用基于内存的算法,否则继续划分。
比如数是32位的,根据每个整数的二进制前5位,划分为32个桶,把数放进对应桶中。如果该桶放不下,继续划分,直至内存可以放心为止。统计每个桶中元素个数,算出中位数一定出现在哪个桶中,而且计算出是该桶中的第几大。