一、在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。
解决方案：桶排序。
1、读入内存2G数据，一个整数四个字节，将这四个字节取最高的一个字节即8位（用>>位移法取出）
2、一个字节共256种可能性，开辟256个文件，根据每个数的高8位写入文件
3、重复上述算法直到所有数算完，同时记录每个文件中的数的数量。
4、第一个文件数的个数+第二个文件数的个数... 可以判断中位数在第几个桶里面
5、把这个桶整个读入内存，之后如果大小小于2G就不用写文件了，在内存中计算就可以
6、这个桶里面的数高8位都一样，用1中的方法去取第二高的字节并重复上面的算法，然后取第三高的字节重复算法，最后一个字节可以接着桶排序，也可以快排，就能得出中位数了
二、10亿个整数，找出最大的1000个。
解决方案：有重复可以用分治法+快排或者小顶堆，如果没有重复可以桶排
1、分治法+快排：将数分成内存能装的下的分数，比如100份，每分进行快排得到最大的1000个，然后将100*1000个数进行快排取1000个。这里快排方法如下：每趟快排可以将数组分成数量不一定的两部分，如果大的那份多余1000，再对着分进行一次快排，如果再多再对多的那份快排一次，如果少了则对少的这份快排一次，如此循环直到够1000个为止。
2、小顶堆：先从文件中读取1000个数到内存，建小顶堆，之后依次读取，每读一个数就和堆顶比较，小于堆顶则丢弃，大于堆顶则与堆顶交换再重建堆，直到全部读取完毕。
3、桶排序：按最高位分256个桶，最高的一个应该超过1000个数，再把这个桶拿出来按第二位继续分桶，直到够数了。
大数据问题处理
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
