浏览 6908 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2010-04-03
最后修改:2010-04-07
此问题可以引申为:
思考了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 详细见图 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2010-04-06
数学不好,不知道这道题目可不可以这样解:
如果上述逻辑可行,那程序就非常简单啊,读取一次文件就可以了。 |
|
返回顶楼 | |
发表时间: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会谁递归发生改变 |
|
返回顶楼 | |
发表时间:2010-04-06
一道算法题,比较简单,就是应用快排的思想。关于快排,不多说。
某个数的位置相当于文件指针吧,整个文件当成数组就可以。 |
|
返回顶楼 | |
发表时间: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" |
|
返回顶楼 | |
发表时间:2010-04-06
楼上的步骤明显有问题。
|
|
返回顶楼 | |
发表时间:2010-04-06
有什么问题?有些错别字,但总体上没有问题吧
|
|
返回顶楼 | |
发表时间:2010-04-07
study2009 写道
呵呵,和前面腾讯面试题一样啊.
一个可以保证最坏运行时间为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"
没什么大问题。 lz的方法有问题,不用排序,也不需要treeset。 另外一个方法是,先分成内存可操作的合适大小的块,比如1G内存,每次load 大概700-800M的数据量, 然后按这个标准切割所有数据分块。 每块内,使用类似快排的方式,找到中位数,o(块的length) 然后各个块的中位数最大的那个,可以去掉一半的数据,最小的那个,也可以去掉一半数据。 去掉后,再找中位数,再比较。 迭代。 即可。 平均应该是o(N)的。
|
|
返回顶楼 | |
发表时间:2010-04-07
最后修改: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肯定是不合理的!因为可能存在相同的数 看样子需要实现一下来进行测试才好阿^ ^ |
|
返回顶楼 | |