腾讯 认领
计算机/互联网/通信/电子 广东 1000人以上 国企/上市公司
从海量数据中找出中位数 (2009-08-06 22:13) 分类： 算法
从海量数据中找出中位数 (2009-08-06 22:13) 分类： 算法 题目：在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可（内存限制为 2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。分析：明显是一道工程性很强的题目，和一般的查找中位数的题目有几点不同。1. 原数据不能读进内存，不然可以用快速选择，如果数的范围合适的话还可以考虑桶排序或者计数排序，但这里假设是32位整数，仍有4G种取值，需要一个16G大小的数组来计数。2. 若看成从N个数中找出第K大的数，如果K个数可以读进内存，可以利用最小或最大堆，但这里K=N/2,有5G个数，仍然不能读进内存。3. 接上，对于N个数和K个数都不能一次读进内存的情况，《编程之美》里给出一个方案：设k
正在加载验证码...
进行了困难电话面试
面试问题
从海量数据中找出中位数 (2009-08-06 22:13) 分类： 算法
面试过程
从海量数据中找出中位数 (2009-08-06 22:13) 分类： 算法 题目：在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可（内存限制为 2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。分析：明显是一道工程性很强的题目，和一般的查找中位数的题目有几点不同。1. 原数据不能读进内存，不然可以用快速选择，如果数的范围合适的话还可以考虑桶排序或者计数排序，但这里假设是32位整数，仍有4G种取值，需要一个16G大小的数组来计数。2. 若看成从N个数中找出第K大的数，如果K个数可以读进内存，可以利用最小或最大堆，但这里K=N/2,有5G个数，仍然不能读进内存。3. 接上，对于N个数和K个数都不能一次读进内存的情况，《编程之美》里给出一个方案：设k