100亿零1个数找中位数 最少读几次磁盘

本文主要是介绍100亿零1个数找中位数 最少读几次磁盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2g内存，磁盘上有100亿零1个32bit 的uint，找中位数，要求读磁盘次数最少

---

很容易想到桶排序，问题是桶的宽度。

由于统计个数，某个桶内可能超过100亿，所以int不行，必须long long
2g内存能放多少long long呢？

2g内存 = $2\ast 2^{10}M$=$2\ast 2^{20}K$=$2\ast 2^{30}bytes$（刚开始脑子秀逗，认为2g内存 = $2\ast 2^{3}M$=$2\ast 2^{6}K$=$2\ast 2^{9}bytes$，注意这里底数是2啊，不是10。。。），而long long占$2^{3}bytes$，所以可以申请$\frac{2^{31}}{2^3}=2^{28}$个桶。uint32是$2^{32}$
，所以桶的宽度是16。

所以，两次读磁盘就够了。。。

这篇关于100亿零1个数找中位数 最少读几次磁盘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---