10G的文件里都是乱序的整数，要求找出中位数。

问题帖子：10G的文件里都是乱序的整数，要求找出中位数

此问题可以引申为：

1. 数据不一定为整数，而是任何个比较的数据
2. 查找第N个数

思考了2个小时 我的思路

输入所有数据,返回第dataSize/2个值

-->分段读取数据-->分成N等分已经排好序的(保存每一段的最大，最小，中值，作为切分值点)

-->依次取N等分 使用切分值点切分追加到文件split(i)中 i表示第i个切分点

-->得到中间值所在的区间split(i) 好了现在回到了初始状态了，需要获取的是数据集split(i)的第(dataSize/2 - sum(i-1))个值;sum(i)=sum(i-1) + split(i).size

详细见图

评论

8 楼 skzr.org 2010-04-07  

10G样本，按2G为一组
第1组:[1, 10G] 2G个
第2组:[2, 10G - 1]2G个
第3组:[3, 10G - 2]2G个
第4组:[4, 10G - 3]2G个
第5组:[5, 10G - 4]2G个
我的treeset只是需要一个合理的分割值而已，用于对10G数据进行合理的分割用
至于排序，这里使用treeset肯定是不合理的！因为可能存在相同的数

看样子需要实现一下来进行测试才好阿^ ^

7 楼 kimmking 2010-04-07  

<div class="quote_title">study2009 写道</div>
<div class="quote_div">呵呵，和前面腾讯面试题一样啊. <br><br>一个可以保证最坏运行时间为O(n)的算法，叫做 "Median of Medians algorithm" <br><br>1.将这n个元素分为5个一组，找出每组里的中间数，形成新的n/5亿个中间值组成的集合 <br>   2.对这n/5个值再分为5个一组，找出每组中间的数...重复这些步骤，只至找的到最后的中间值m <br>   3.以m为中值，将n个数分为L,R两组，L集合里的数都小于m,R集合里的数都大于m <br>     如果m=n/2，则返回m <br>     否则 如果L集合里的数多余一半，则从L集合中找出第n/2小的数 <br>          如果R集合里的数多余一半，R集合的元素个数为k, 则从R集合中找出第k-n/2小的数. <br>   4.如此重复迭代调用，直至找到中值. <br><br>网上可以找到该算法实现的源代码,多为内存排序,但也比较容易改为外排序. <br><br>对这个问题详细探讨间Blum, Floyd, Pratt, Rivest, and Tarjan 在1973年发表 <br>的论文"Time bounds for selection",这篇文章很难看懂. <br>也可以直接搜索"Median of Medians algorithm" <br><br><br>
</div>
<p> </p>
<p> 没什么大问题。</p>
<p>lz的方法有问题，不用排序，也不需要treeset。</p>
<p>另外一个方法是，先分成内存可操作的合适大小的块，比如1G内存，每次load 大概700-800M的数据量，</p>
<p>然后按这个标准切割所有数据分块。</p>
<p>每块内，使用类似快排的方式，找到中位数，o(块的length)</p>
<p>然后各个块的中位数最大的那个，可以去掉一半的数据，最小的那个，也可以去掉一半数据。</p>
<p>去掉后，再找中位数，再比较。</p>
<p>迭代。</p>
<p>即可。</p>
<p>平均应该是o(N)的。</p>
<p> </p>
<p> </p>
<p> </p>

6 楼 study2009 2010-04-06  

有什么问题?有些错别字，但总体上没有问题吧

5 楼 kimmking 2010-04-06  

楼上的步骤明显有问题。

4 楼 study2009 2010-04-06  

呵呵，和前面腾讯面试题一样啊.

一个可以保证最坏运行时间为O(n)的算法，叫做 "Median of Medians algorithm"

1.将这n个元素分为5个一组，找出每组里的中间数，形成新的n/5亿个中间值组成的集合
   2.对这n/5个值再分为5个一组，找出每组中间的数...重复这些步骤，只至找的到最后的中间值m
   3.以m为中值，将n个数分为L,R两组，L集合里的数都小于m,R集合里的数都大于m
     如果m=n/2，则返回m
     否则 如果L集合里的数多余一半，则从L集合中找出第n/2小的数
          如果R集合里的数多余一半，R集合的元素个数为k, 则从R集合中找出第k-n/2小的数.
   4.如此重复迭代调用，直至找到中值.

网上可以找到该算法实现的源代码,多为内存排序,但也比较容易改为外排序.

对这个问题详细探讨间Blum, Floyd, Pratt, Rivest, and Tarjan 在1973年发表
的论文"Time bounds for selection",这篇文章很难看懂.
也可以直接搜索"Median of Medians algorithm"

3 楼 worldterminator 2010-04-06  

一道算法题，比较简单，就是应用快排的思想。关于快排，不多说。
某个数的位置相当于文件指针吧，整个文件当成数组就可以。

2 楼 skzr.org 2010-04-06  

10G的文件里都是乱序的整数
都是乱序的整数！就是这一点，根本无法保证
中序值一定出现在这两个整数中(当缓存数组装满时，对数组进行排序，并取出中间的两个整数，保存)

比如缓存可以取2G,那么可以分5组，对应的值所在区间分别为
第1组:[1, 10G]
第2组:[2, 10G - 1]
第3组:[3, 10G - 2]
第4组:[4, 10G - 3]
第5组:[5, 10G - 4]
那就麻烦了

我的思路就是一步一步去第N个值肯定不在的区间！那么第n个值一定在剩余的区间中！从而问题回到递归开始，只是这个位置N会谁递归发生改变

1 楼 夜是天堂 2010-04-06  

数学不好，不知道这道题目可不可以这样解：

• 根据可用内存大小，设置一个缓存数组，数组长度为偶数
• 顺序读取文件，将整数逐个放入缓存数组
• 当缓存数组装满时，对数组进行排序，并取出中间的两个整数，保存
• 清空缓存数组，重复执行2-3
• 如果最后一批无法装满缓存数组，需要特殊处理：
• 重新构造一个数组，使其长度等于剩下整数的个数
• 对新的数组进行排序
• 如果数组长度为偶数，取中间两个整数，否则取最中间的那个整数，保存
• 对上述保存的所有中间数字进行排序，这些数字的中位数是不是就等于所有整数序列的中位数？

如果上述逻辑可行，那程序就非常简单啊，读取一次文件就可以了。