- 浏览: 366071 次
- 性别:
- 来自: 长沙
文章分类
- 全部博客 (186)
- J2EE (46)
- spring (4)
- Applet (7)
- 网页前端 (10)
- 生活与工作 (55)
- 开放的世界 (10)
- linux (16)
- j2me (2)
- android (5)
- ExtJS (1)
- 架构师与设计 (7)
- 开发平台 (2)
- Eclipse (4)
- 教育 (0)
- 数据库 (9)
- English (1)
- Jetty (2)
- 未分类 (1)
- 工具 (2)
- flex (2)
- synchronized (1)
- maven (2)
- command (0)
- shell (1)
- web (1)
- qq (3)
- wine (3)
- chrome (1)
- extensions (1)
- plugin (1)
- 插件 (1)
- ssh (1)
- 内网 (1)
- J2EE excel (1)
- ubuntu (4)
- storm (2)
- hadoop (1)
最新评论
-
skzr.org:
jdbc:mysql://localhost:3306/?us ...
storm topology all in one spring文件合并 -
chenghong726:
你好,我用你这个方法,上传文件72M一直卡在 mapper.s ...
超大excel读取 43万记录 26M文件 -
海hai:
您好我对这篇文章很敢兴趣可以和你请教下吗?我qq9034418 ...
淘宝top自动授权页面,方便大家调试top应用 -
skzr.org:
首先感谢你的关注:)yaerfeng1989 写道最代码上有更 ...
[MAVEN]web工程的调试 -
skzr.org:
最新消息2013-12-17:腾讯再次弹出消息,我的QQ201 ...
ubuntu 12.04安装QQ2012
此问题可以引申为:
- 数据不一定为整数,而是任何个比较的数据
- 查找第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肯定是不合理的!因为可能存在相同的数
看样子需要实现一下来进行测试才好阿^ ^
第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>
<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"
一个可以保证最坏运行时间为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会谁递归发生改变
都是乱序的整数!就是这一点,根本无法保证
中序值一定出现在这两个整数中(当缓存数组装满时,对数组进行排序,并取出中间的两个整数,保存)
比如缓存可以取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
- 如果最后一批无法装满缓存数组,需要特殊处理:
- 重新构造一个数组,使其长度等于剩下整数的个数
- 对新的数组进行排序
- 如果数组长度为偶数,取中间两个整数,否则取最中间的那个整数,保存
- 对上述保存的所有中间数字进行排序,这些数字的中位数是不是就等于所有整数序列的中位数?
如果上述逻辑可行,那程序就非常简单啊,读取一次文件就可以了。
发表评论
-
买了两山地车,骑车上下班。
2011-03-29 22:19 1275今天早上累死了终于没有迟到,不过打卡已经8:33了。 晚上回 ... -
core i7 + 4X2G DDR3 + Nvidia 2G独显 本本想入手阿
2011-03-27 22:06 1002呵呵,如题! 貌似现在还比较贵,等 -
病不起 :)
2011-03-27 16:33 971无奈中-国-国-情的经验: 到医院不如到药店找售货的,人家简 ... -
准备进入另一个山头,留发纪念
2011-03-23 12:58 1161纪念2004-2010年流逝的岁月 -
2011年2月感触——思感提升30了阿
2011-02-13 21:22 1137转眼2011年了,呵呵步入人生的第30个年头 回 ... -
答复: 当你在进步而朋友原地不动时
2011-02-07 20:14 978论坛原文 iapple 写道刚好看到一位读者在 “Having ... -
生活是靠走的
2011-01-25 09:02 1081早上不知道怎样,想什么是人生曲线,低谷和山峰在哪儿,难道 ... -
心中疑问的思考?
2011-01-23 23:23 789工作感觉不得力,感 ... -
咳嗽 飞龙止咳
2010-12-19 14:38 11832010年CSDN上海软件开发者大会,飞龙 健康讲座 ... -
[转]迈向架构师的第一步
2010-11-25 15:20 969原文:CSDN ID:cutesource http:// ... -
[转]程序员不成熟的若干个特征
2010-11-25 15:16 739原文地址:CSDN 尹成 ... -
前行的路
2010-11-16 21:39 869时间一点一点的走过,心路一点一点的在拓展 走入社会身边的亲人 ... -
服务设计 谈论1
2010-11-11 11:50 813我一直觉得只有符合业 ... -
[心情很糟]体会到心情很糟阿,my life my choice!
2010-11-09 13:10 1085心情极度郁闷,忧郁 I have nothing, b ... -
0分作文——2010年普通高等学校招生考试上海卷作文题
2010-10-04 11:18 928此人是个人才 :) 2010 ... -
面向对象,真的必须设计数据对象吗?
2010-09-28 17:00 1747开发:JAVA 现在越来越觉得自己把dao或者是orm ... -
发展规律——由弱到强
2010-09-05 11:54 1146对于穷二代来说,创业是不容易的,最大的挑战来自家庭,其次才是金 ... -
在博源的日志——结束
2010-08-14 16:46 9172010-08-14日星期六 昨天是在博源的最后一天,在 ... -
在博源的日志——第3天
2010-08-12 10:24 11092010-08-11 博源第3天 一天我不知道自己做 ... -
在博源的日志——第一天
2010-08-12 10:23 9042010-08-09 博源第一天 一个大的办公室,大约50人 ...
相关推荐
找出一组数(N 个整数,N,未排序)的中位数。
3位正整数中,既是完全平方数,又有两位数相同,如144,676等,找出所有这样的数。
如果要求的中位数是“四分位数”,则还需要考虑第3个元素(下标为2)作为第一四分位数(Q1)和第7个元素(下标为6)作为第三四分位数(Q3)。 4. **输出结果**:将计算出的中位数打印出来。在一些编程环境中,可能...
首先,问题描述提出了一个典型的约束条件:一个10GB的文件包含了10亿个乱序排列的整数,而可用内存只有2GB。因此,不能将所有数据一次性加载到内存中进行排序。针对这个问题,文章提出了一种创新的解决方案。 该...
给定程序中,函数fun的功能是:在任意给定的9个正整数中找出按升序排列是处于中间的数,将原数据序列中比该中间数小的数用该中间数替换,位置不变,在主函数中输出处理后的数据序列,并将中间数作为函数值返回。...
本篇将详细探讨如何使用C语言来找出给定一系列整数中的最小值,这对于初学者来说是一项基础但重要的任务。 首先,我们需要了解C语言的基本语法和数据类型。C语言中的整数类型通常有`int`,它能够存储正负整数。为了...
中位数定义:一组数据按从小到大的顺序依次排列,处在中间位置的一个数(或最中间两个数据的平均数). 给出一组无序整数,求出中位数,如果求最中间两个数的平均数,向下取整即可(不需要使用浮点数)
例如,1,2,5,10 都是正整数10 的约数,且div(10)=4。设a 和b 是2 个正整数,a≤b,找出a 和b之间约数个数最多的数x。 编程任务:对于给定的2 个正整数a≤b,编程计算a 和b 之间约数个数最多的数。 Input 输入...
C语言程序设计-从键盘为一维整型数组输入10个整数,调用fun函数找出其中最小的数,并在main函数中输出;本.cC语言程序设计-
标题中的“整数数位和”指的是计算一个整数所有数位上的数字之和。在编程领域,这是一项常见的操作,常用于各种算法或数学问题的解决方案中。例如,求一个数的数字和可以帮助我们快速判断它是否为回文数,或者在计算...
C语言程序设计-从键盘为一维整型数组输入10个整数,调用fun函数找出其中最小的数,并在main函数中输出;请编写fun函数;.c
列表存放n个整数,计算它的中位数。
# 题目: # 给一个不多于5位的正整数,要求:一、求它是几位数,二、逆序打印出各位数字。 # 分析: # 学会分解出每一位数。
给定一个整数n(1≤n≤100000000),要求从个位开始分离出它的每一位数字。从个位开始按照从低位到高位的顺序依次输出每一位数字。 【输入】 输入一个整数,整数在1到100000000之间。 【输出】 从个位开始按照从低位...
数组a中已存有互不相同的10个整数从键盘输入一个整数,找出与该值相同的数组元素下标。 (如果没找到,输出“没找到”).c
取模运算返回的是两数相除后的余数,因此`num % 10`总是会得到`num`的最后一位。然后,我们通过整除运算 `/=` 将`num`的个位数移除,以便在下一次迭代中处理下一位数字。这个过程会一直持续到`num`变为0为止,此时...
例如,十进制数5在二进制中是101,十进制数-5在二进制补码表示法中是11111011。位数是指这个二进制表示中1的个数,对于非负整数,位数就等于其在十进制表示下的位数;对于负数,我们通常只关注其绝对值的位数。 ...
在C语言中,中位数是指一组数据按照升序或降序排列后位于中间位置的数值。如果数据的个数是奇数,则中位数是正中间的那个数;如果是偶数,则中位数通常取中间两个数的平均值。这个题目涉及到的核心知识点包括数组...
C语言程序设计-找出一批正整数中的最大的偶数;
3. 计算位数:要找出整数的位数,我们可以使用数学的对数运算和整数除法。首先,计算自然对数,然后取整,再加1即可得到位数。但Delphi没有内置的自然对数函数,我们可以使用Ln函数结合常数e来近似计算: ```delphi...