这道题要在512M内存里找出100亿个乱序的32位整数的中位数。系统只给了512M空间，100亿个数这么大，想用一次性把它们全读到内存里再排序，那肯定得爆内存。那512M内存到底能装多少数呢？1个int占4字节，512M就是512乘以1024再乘以1024字节。算下来，最多也就能同时装下约1.34亿个数，所以把所有数一口气读完是行不通的。那该怎么办？只能把43亿个值平均分成10万个子区间，每个区间大约有43000个数。先把第一组的1亿个数读进来，用哈希表或者桶排序的方法统计它们落在哪个子区间里。接着再把剩下的99组数据分批读进来，边读边更新各个子区间的计数。当累计的总数第一次超过50亿的时候，这个区间就是第50亿个数所在的位置，记为ai。然后把前面所有区间的计数加起来，如果超过50亿了，那ai前面那个区间就是“中位数前半部”的终点。 具体来说，先把整个整数范围[-2^31, 2^31-1]的4294967296个值平均切成10万块“小蛋糕”，每个小蛋糕对应一个子区间。第一次读进约1亿个数后，后面还要循环99次每次都读约1亿个数。累计和要用long long型变量存起来防止溢出。当累计和达到50亿时锁定ai区间。 最后一步是在ai区间内做一次缩小版的计数排序。把这43000个数当成43000个“小区间”，再次统计每个“小区间”里有多少数。当累计和达到50亿减去前面的总数时，这个“小区间”里的数就是中位数了。 如果这个数的位置是奇数的话就直接取中间的那个数；如果是偶数的话就取中间两个数的平均值。 时间复杂度方面，读入和统计大概需要2亿次单点判断（耗时约6秒），二次计数排序大概需要4万次单点判断（耗时约1秒），总耗时大约是7秒。空间方面除了哈希表或桶排序的开销大约4MB外剩下的空间完全足够缓存中间结果。 通过分而治之加二分搜索的策略把看似不可能的大任务拆分成可管理的小任务就能搞定这个问题了。