问题
有5亿个整数,没有排序。找到他们的中位数
思路
使用双层桶划分(分而治之)的策略。假设题目中指的是32位的无符号整数,共有2 ^ 32个数字。
我们将2 ^ 32这个范围划分成2 ^ 10个区域。对数据进行第一次扫描,统计各个落到各个区域内的数字的个数。
第一次扫描后,通过统计就可以知道,中位数在哪个区域内,以及它是这个区域的第几大的数字。
进行第二次扫描,这次只统计落到目标区域内的数字,同时结合Bitmap记录都出现了哪些数字。最后通过Bitmap和第一次扫描的结论,就可以找到那个中位数了。