发表于：2007-10-10 13:28:21 楼主
在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。
问题点数：50 回复次数：100 显示所有回复显示星级回复显示楼主回复
zgg___
等 级：
发表于：2007-10-10 13:49:471楼 得分:0
这10G个整数是什么样的整数呢？是每个都是int型的，还是每个都有1000000位的整数呢？如果题目没有说明，就只能按最糟糕的情况来理解吧？不过题目说是在一个文件中，就又貌似还有实际情况的转机。呵呵。
tailzhou
尾巴
等 级：
发表于：2007-10-10 14:23:502楼 得分:0
2G内存大约能保存500M个整数（假设整数为32位）；
可以将这10G个整数按照大小分放到N个文件中，并记录每个文件的数字的个数，这样就可以计算出中位数应该在第i个文件中的第j大的数；
若文件中的数的个数小于500M，有O(N)的方法直接在内存中查找第j大的数；
若文件中的数的个数小于500M，继续分解；
flushtime
Eastsun
等 级：
发表于：2007-10-10 14:24:503楼 得分:0
不知道整数的范围,有点麻烦.
可以试试这样
int *count =new int[RANGE]; //RANGE表示其中整数的范围
然后 memset(count,0,sizeof(count));
扫描一遍文件,读入整数num,
count[num] ++; //可能需要对num进行适当偏移
扫描完后:
int sum =0;
for(int index =0;index <RANGE&&sum < 1G -1; index++) sum += count[index];
这个index即为所求:
cout < <index;
kaishui_gu
开水
等 级：
发表于：2007-10-10 14:28:354楼 得分:0
折半排序
zgg___
等 级：
发表于：2007-10-10 14:51:055楼 得分:0
按照“最糟糕的情况”，我们把2G内存（=16Gbit）中的10Gbit都用来为10G个数做标记上（简称标记）。一开始，所有的标记都为0。我们先把10G个数分为2G组，每组5个，分别求每组的中位数，将其中不是中位数的8G个数的标记都置为1，这一步的时间复杂度为O（n）。这样就还剩2G个标记为0的数，再次分组，排除掉一批数。这样循环下去，直到求出结果。如果中间有时剩下2、3个数无法分组，就保留着，直接进入下一轮的循环。循环的次数是lg（n）量级，所以总的算法时间复杂度是O（nlgn）。
对于本个问题，O（nlgn）和O（n）的算法相差不大，因为这里的n（=10G）太小了，呵呵。不过，继续寻求O（n）复杂度的算法是非常有趣的。
tailzhou
尾巴
等 级：
发表于：2007-10-10 15:47:156楼 得分:0
zgg_的方法好象有点问题：
10G个数的中位数并不一定是 （2G组，每组5个，分别求每组的中位数）中的数；
zgg___
等 级：
发表于：2007-10-10 16:11:237楼 得分:0
的确是有严重的问题。
我5楼的方法是错误的，是我没有想清楚。
感谢tailzhou指正。
mathe
void
等 级：
发表于：2007-10-10 17:22:398楼 得分:0
It is easy to design an O(nlogn) algorithm.
First count number of 1 in the highest bit of all 10G numbers.
If the number is more than 5G, the highest bit of median is 1 otherwise the highest bit of median is 0.
Next we need to find the p-th largest number in a subset while the highest bit of all numbers are same (all other number is ignored)
The 2nd pass to count number of 1 in the 2nd highest bit of numbers in the subset.
According to the previous too result, we could find the value of 2nd highest bit of the median.
...
When the 32nd pass is finished, we could get the median.
In fact, in the middle of the algorithm, when we find that the numbers left in subset is no more than 512M, we could read all of them into 2G memory and using O(n) algorithm to find the median.
kaishui_gu
开水
等 级：
发表于：2007-10-10 17:31:519楼 得分:0
设最大数为N；只要将数据按N/2分成两组，大于N/2或小于N/2，这样一直分就可以找到，
wangling21908
浪迹
等 级：
发表于：2007-10-10 22:31:3510楼 得分:0
二分法
oo
为了名副其实，努力学习oo技术ing
等 级：
发表于：2007-10-10 23:10:1911楼 得分:0
1，把整数分成256M段，每段可以用64位整数保存该段数据个数，256M*8 = 2G内存，先清0
2，读10G整数，把整数映射到256M段中，增加相应段的记数
3，扫描256M段的记数，找到中位数的段和中位数的段前面所有段的记数，可以把其他段的内存释放
4，因中位数段的可能整数取值已经比较小（如果是32bit整数，当然如果是64bit整数的话，可以再次分段），对每个整数做一个记数，再读一次10G整数，只读取中位数段对应的整数，并设置记数。
5，对新的记数扫描一次，即可找到中位数。
如果是32bit整数，读10G整数2次，扫描256M记数一次，后一次记数因数量很小，可以忽略不记
chinacommander
等 级：
发表于：2007-10-11 08:41:0212楼 得分:0
11楼的做法不错
mmmcd
超超
等 级：
发表于：2007-10-11 09:27:1713楼 得分:0
不错
方法正如11楼所说
kaishui_gu
开水
等 级：
发表于：2007-10-11 09:44:3114楼 得分:0
11楼的算法比较复杂，很多地方看不懂，有没有人可以解析下
整数分成256M段？
整数映射到256M段中？
oo
为了名副其实，努力学习oo技术ing
等 级：
发表于：2007-10-11 09:53:2115楼 得分:0
kaishui_gu
开水
等 级：
发表于：2007-10-11 09:44:3114楼 得分:0
11楼的算法比较复杂，很多地方看不懂，有没有人可以解析下
整数分成256M段？
整数映射到256M段中？
======================
假设是32bit整数，按无符号整数处理
整数分成256M段？ 整数范围是0 - 2^32 - 1 一共有4G种取值，4G/256M = 16，每16个数算一段 0-15是1段，16-31是一段，...
整数映射到256M段中？ 如果整数是0-15，则增加第一段记数，如果整数是16-31，则增加第二段记数，...
其实可以不用分256M段，可以分的段数少一写，这样在扫描记数段时会快一些，还能节省一些内存
ilovechao1314
有点晕了
等 级：
发表于：2007-10-11 10:03:4416楼 得分:0
中位数是什么意思？
kaishui_gu
开水
等 级：
发表于：2007-10-11 10:14:2117楼 得分:0
谢谢OO的回答，明白了，真的不错。
tailzhou
尾巴
等 级：
发表于：2007-10-11 10:25:5218楼 得分:0
mathe的方法就跟oo的分成2段的时候是一样的；
我决得还是拆分到不同的文件中效率要好一点；
不拆分每次需要遍历10G个数据
拆分后只需要遍历相应范围内的数据；
假设数据是均匀分布的；
不拆分的平均复杂度是O(nlogn)
拆分后的平均复杂度应该是O(n);
tailzhou
尾巴
等 级：
发表于：2007-10-11 10:29:5519楼 得分:0
当拆分后的数据可以用2G内存来保存的时候，就可以直接在内存中进行查找了；
“In fact, in the middle of the algorithm, when we find that the numbers left in subset is no more than 512M, we could read all of them into 2G memory and using O(n) algorithm to find the median. ”
oo
为了名副其实，努力学习oo技术ing
等 级：
发表于：2007-10-11 10:34:0220楼 得分:0
to tailzhou 尾巴 :
文件写比文件读慢不少的。即便速度差不多，写一次至少相当于读一次。
qisamuelzhang
Samuel
等 级：
发表于：2007-10-11 10:42:4821楼 得分:0
如果记得没错，编程珠玑中第一个问题就是内存限制的整数排序，然后取中位数便简单了。
tailzhou
尾巴
等 级：
发表于：2007-10-11 11:33:1822楼 得分:0
是要多出一些文件写的操作；
但数据量要小很多呀，也就是少了更多的读文件的操作；
superdullwolf
狼群
等 级：
发表于：2007-10-11 11:49:0723楼 得分:0
把整数分成x段(比如x=256M),每段找最大最小O(n),得到2个256M长数组
再在这2个数组中分别找最大最小.O(n),
得到 中位数=最大+最小/2.
遍历x段看这个中位数有没有有了就退出,没有就选择 中位数=min( ¦i-中位数 ¦)O(n)
怎么弄都是O(n).
superdullwolf
狼群
等 级：
发表于：2007-10-11 11:56:5724楼 得分:0
内存限制为 2G,根本用不上,2M都够了.
想分多小内存都可以.
只要我分段足够小,每段占内存+2个数组的内存占有量 <目标内存数就够了.
superdullwolf
狼群
等 级：
发表于：2007-10-11 12:01:4125楼 得分:0
突然想到,根本就没必要保存这个做中间结果的数组,得到最大值最小值再比较一下,直接扔掉其他结果,不需要内存.
所以每段占内存=目标内存
2k都多余了.
superdullwolf
狼群
等 级：
发表于：2007-10-11 12:15:4826楼 得分:0
soryy看错题目了,以为是平均数呢.
Sunrain
NULL
等 级：
发表于：2007-10-11 12:28:3127楼 得分:0
32位?10G?中数？有好几个吧？
qq379699897
等 级：
发表于：2007-10-11 12:39:2728楼 得分:0
汗颜
leoting
tingting
等 级：
发表于：2007-10-11 13:12:3029楼 得分:0
请问上面讨论的同学知道什么叫中位数吗？
若数字的个数是奇数那么（个数+1）/2所对应的那个数就是中位数EG:2 5 6 8 7 4 9 中位数是：（7+1）/2=4 从左数的第4个就是了。
若数字的个数是偶数那么个数/2所对应的那个数+个数/2的商+1所对应的那个数的和的1/2就是这组数据的中位数EG：2 5 4 6 9 8 中位数是：6/2=3 6/2+1=4 也就是（4+6）/2就是中位数了
这根本不是查找也不是排序问题
只是一个简单的运算问题，要考虑的应该是溢出的问题，如何使计算结果正确
以上是我个人看法，不对请指正
谢谢！
laviewpbt
人一定要靠自己
等 级：
发表于：2007-10-11 13:19:1330楼 得分:0
腾讯吃饱了没事干！
wuxing2006
金宝
等 级：
发表于：2007-10-11 13:54:5731楼 得分:0
先做好排序，写到另一个文件中去
然后根据文件长度取出中间那部份
jimmy_w
IBM国际大嘴巴
等 级：
发表于：2007-10-11 14:32:0132楼 得分:0
31楼的。。。。。。
woao
迷茫者
等 级：
发表于：2007-10-11 14:52:4133楼 得分:0
29楼的，你的中位数定义好像有点问题吧？ 应该是排好序后再按你那样定义。
比如现在有一组数据
1，2，3，4，4，5，5，5，6，7，8，8，9，从小到大排好了顺序
一共是13个，其中5有3个，4和6有2个，其他都是1个
中位数，就是这些数据排列好了以后中间的那个数字，比如现在是13个，中间那个应该是第7个，所以就是5，那么如果有偶数个数据，那么就是中间两个数字的平均数，比如说18个数据，就应该是第9位和第10位相加除以2。
11楼的思想确实很不错，赞一个
kevin129
等 级：
发表于：2007-10-11 15:31:5034楼 得分:0
确实每次都读10G整数感觉数据量大了点
fire_woods
风林火山
等 级：
发表于：2007-10-11 16:17:2835楼 得分:0
貌似分成2M段合理一些,这样只需要2M*8=16M的内存可以搞定了.
同时catch命中也会高很多.
fire_woods
风林火山
等 级：
发表于：2007-10-11 16:18:4536楼 得分:0
或者2^16=65536段?
AhJo
AhJo
等 级：
发表于：2007-10-11 16:25:1937楼 得分:0
谢谢大家
我看不懂…………
mathe
void
等 级：
发表于：2007-10-11 17:17:4438楼 得分:0
不错，的确两次扫描数据就可以了。分成2M段的确是最好的办法
sfx123
等 级：
发表于：2007-10-11 17:44:3539楼 得分:0
看不懂
如果在第一次扫描的时候
10g数全部的都是落在同一个段里面 第二次扫描怎么会怎么样?
tailzhou
尾巴
等 级：
发表于：2007-10-11 17:44:5640楼 得分:0
不管是2M还是多少段，
都不能只分一次的；
假设10G个数都一样，分一次没任何作用；
mathe
void
等 级：
发表于：2007-10-11 18:17:4441楼 得分:0
10G个数都一样也没有问题。
还是给个伪代码吧,假设这些整数都是无符号整数,分成64K段
long long Counter[1 < <16];//64K numbers
unsigned int x;
memset(Counter,0,sizeof(Counter));
foreachnumber(x){
Counter[x> > 16]++;
}
long long sum=0;
for(i=0;i <1 < <16;i++){
sum+=Counter;
if(sum> =5LL < <30)break;//More than half, so that Medium in this segment
}
sum-=5LL < <30;
sum=Counter-sum;//Index in the array
int segment=i;
memset(Counter,0,sizeof(Counter));
foreachnumber(x){
if((x> > 16)==segment){
Counter[x&(~((-1) < <16))]++;
}
}
long long lsum=0;
for(i=0;i <1 < <16;i++){
lsum+=Counter;
if(lsum> =sum)break;///Now the medium is found.
}
当然，还有一个特殊情况就是找到的数据所在段正好刚刚凑满5G,这种特殊情况还需要将下一个段最小数据读进来，但是对时间复杂度影响不大。
superdullwolf
狼群
等 级：
发表于：2007-10-11 18:34:1042楼 得分:0
10G是偶数,那么从1开始算排在第5G和5G+1个元素就是你想要的,
分段桶排序-2,147,483,648 到 2,147,483,647 共4294967296个数字=65536*65536,分成 65536个桶的话,每个桶有65536个数字范围.在这个范围内就算砸中.
int[] Arr1=new int[65536]中每个元素分别代表每个桶中落入的数字个数,
例如:
-2,147,483,648到-2147418112是第一个桶,落在里边x0个数字.
-2147418112到-2147352576是第二个桶,落在里边x1个数字.
.....
以上复杂度是O(n).内存需要量是int[65536]占的内存 64k吧,很小.
那么依次可以累积x0+x1+...求出,第5G和5G+1个元素落在哪个桶里.
这段假设就落在了0到65536这个桶,这个桶被砸中了K次,桶里边的中位数k/2 和 (k/2)+1就是最后的中位数.
再创建65536个的桶,int[] Arr2=new int[65536],把10G个数字再投递一遍,每个桶标记下被砸中的次数,累计到2147和就得到了中位数
和上一个桶不一样,这次不是砸某个范围,这次是准确的投递.同样纪录每个桶被砸中的次数
0是第一个桶,落在里边y0个数字.
1是第二个桶,落在里边y2个数字.
....
因为这个桶被砸中了K次,累计y0+y2+...到了k/2 和 (k/2)+1就是最后的中位数.
复杂度还是O(n).全部内存需要64k
superdullwolf
狼群
等 级：
发表于：2007-10-11 18:39:0343楼 得分:0
第一个数组用完,把k和中位数范围纪录下来就可以扔掉了.所以内存还是64k.
superdullwolf
狼群
等 级：
发表于：2007-10-11 19:45:2344楼 得分:0
using System;
using System.IO;
namespace Median
{
class Program
{
static void Main(string[] args)
{
//这程序编译通过，但是我没运行，虽然复杂度是O(n)占用64k多一点内存。
//我可不想写那么多文件，还费我那么多时间去运行它。
//运行前先写文件，写了就不要再写了；
writeFile();
int[] Arr = new int[65536];
//循环读文件65536个，10个G数字，每个文件读到结尾，复杂度是O(N) ,N=10G
for(int x=0;x <65536;x++)
{
string FileName = @"C:\" + x + ".txt";
FileStream FileReader = new FileStream(FileName, FileMode.Open);
//去读文件，每次读4个字节一个整数。
int index = 0;
while (index < 65536*4)
{
byte[] tempByte = new byte[4];
index += FileReader.Read(tempByte, 0, 4);
int tempInt = System.BitConverter.ToInt32(tempByte, 0);
Arr[(tempInt - int.MinValue) / 65536]++;
}
FileReader.Close();
}
double MedianBarrel = 0;
int theBarrelIndex = 0;
//复杂度是O(m) ,m=65536
for (int i = 0; i < Arr.Length; i++)
{
MedianBarrel += Arr;
if (MedianBarrel > = 5000000000)
{
//找到中位数所在的桶的索引；找到就退出
theBarrelIndex = i;
break;
}
}
//中位数所在的桶的最小元素是theBarrel*65536，最大是(theBarrel+1)*65536落在里边有k个数字。
int K = Arr[theBarrelIndex];
Arr = new int[65536];
//去读文件，每次读4个字节一个整数。
//复杂度是O(N) ,N=10G
for (int x = 0; x < 65536; x++)
{
string FileName = @"C:\" + x + ".txt";
FileStream FileReader = new FileStream(FileName, FileMode.Open);
int index = 0;
while (index <= 65536 * 4)
{
byte[] tempByte = new byte[4];
index += FileReader.Read(tempByte, 0, 4);
int tempInt = System.BitConverter.ToInt32(tempByte, 0);
Arr[tempInt - theBarrelIndex * 65536]++;
}
FileReader.Close();
}
//关键时刻到了
int Median = 0;
int result1; int result2;
//复杂度是O(m) ,m=65536中途找到了就退出。
for (int i = 0; i < 65536; i++)
{
Median+=Arr;
if (Median > = K / 2)
{
//得到那该死的两个数字
result1 = i + theBarrelIndex * 65536;
result2 = i + theBarrelIndex * 65536+1;
Console.WriteLine(result1);
Console.WriteLine(result2);
Console.WriteLine("全部复杂度是O(N),N=10G,内存占用64k多一点");
Console.ReadLine();
break;
}
}
}
public static void writeFile()
{
//写65536个文件，用来实验的；写一遍就可以了。
//腾讯不会那么傻把10G个数字存储到一个文件里
//应该存储到65536文件，每个文件65536个数字。
for (int x = 0; x < 65536; x++)
{
FileStream FileWriter = new FileStream(@"C:\" + x + ".txt", FileMode.OpenOrCreate);
System.Random rand = new Random();
for (int i = 0; i < 65536; i++)
{
int tempInt = rand.Next(int.MinValue, int.MaxValue);
FileWriter.Write(System.BitConverter.GetBytes(tempInt), 0, 4);
}
FileWriter.Close();
}
Console.WriteLine("写文件完毕！");
}
}
}
sfx123
等 级：
发表于：2007-10-11 21:27:1645楼 得分:0
如果前面j个桶合计被砸中4g次,j+1个桶被砸中6g次,那么中位数字就是j+1个桶的排第6g/2=3g位的那个数?
应该要记住前j个桶中被砸中多少次,然后再用5g-这个次数,得到的这个数才是中位数在j+1排的位置
还有就是纪录每个桶被被砸中的次数的整数必须用64位整数吧.因为10g> 2^32
ps:可能是我这个菜鸟理解错了,我也没仔细看代码......
不过感觉总体思路就是11楼说的
tailzhou
尾巴
等 级：
发表于：2007-10-11 22:48:4146楼 得分:0
确实象mathe那样分2^16段效率要好；
第一次对前１６位相同的数记数；找到中位数的前１６位；
以该１６位开头的数按照后１６位计数；
这样两次记数用的内存一样多；
其他的分法总有一次记数比这样的分法用的内存要多
superdullwolf
狼群
等 级：
发表于：2007-10-12 00:07:5347楼 得分:0
修改了一下,
1,正如sfx123 说的那样,可能每个桶被砸中的次数超过了整数范围.
2,10G个数字要写1万个文件,每个1M.
3,还有点疑问:如果1,2,2,2,2,2,2,3,4,5,8,10这样重复的数字中中位数到底算是2,2还是2,3,还是4,我没太搞明白.
C# code
using System;
using System.IO;
class Program
{
static void Main(string[] args)
{
//这程序编译通过，但是我没运行，虽然复杂度是O(n)占用64k多一点内存。
//我可不想写那么多文件，还费我那么多时间去运行它。
//运行前先写文件；
writeFile();
double[] Arr = new double[65536];
//循环读文件10000个，10个G数字，每个文件读到结尾，复杂度是O(N) ,N=10G
for (int x = 0; x < 10000; x++)
{
string FileName = @"C:\" + x + ".txt";
FileStream FileReader = new FileStream(FileName, FileMode.Open);
//去读文件，每次读4个字节一个整数。
int index = 0;
while (index < 1000000 * 4)
{
byte[] tempByte = new byte[4];
index += FileReader.Read(tempByte, 0, 4);
int tempInt = System.BitConverter.ToInt32(tempByte, 0);
Arr[(tempInt - int.MinValue) / 65536]++;
}
FileReader.Close();
}
double MedianBarrel = 0;
int theBarrelIndex = 0;
//复杂度是O(m) ,m=65536
for (int i = 0; i < Arr.Length; i++)
{
MedianBarrel += Arr;
if (MedianBarrel >= 5000000000)
{
//找到中位数所在的桶的索引；找到就退出
theBarrelIndex = i;
break;
}
}
//中位数所在的桶的最小元素是theBarrel*65536，最大是(theBarrel+1)*65536落在里边有k个数字。
//K是中位数那个桶被砸中的次数，如果数字超过整数就不好玩了。
double K = Arr[theBarrelIndex];
Arr = new double[65536];
//去读文件，每次读4个字节一个整数。
//复杂度是O(N) ,N=10G
for (int x = 0; x < 10000; x++)
{
string FileName = @"C:\" + x + ".txt";
FileStream FileReader = new FileStream(FileName, FileMode.Open);
int index = 0;
while (index <= 1000000 * 4)
{
byte[] tempByte = new byte[4];
index += FileReader.Read(tempByte, 0, 4);
int tempInt = System.BitConverter.ToInt32(tempByte, 0);
Arr[tempInt - theBarrelIndex * 65536]++;
}
FileReader.Close();
}
//关键时刻到了
double Median = 0;//用double类型，因为真的可能被砸中超过整数范围次数。
int result1; int result2;
//复杂度是O(m) ,m=65536中途找到了就退出。
for (int i = 0; i < 65536; i++)
{
Median += Arr;
if (Median >= theBarrelIndex * 65536 + int.MinValue + K / 2)
{
//得到那该死的两个数字
result1 = i + theBarrelIndex * 65536;
result2 = i + theBarrelIndex * 65536 + 1;
Console.WriteLine(result1);
Console.WriteLine(result2);
Console.WriteLine("全部复杂度是O(N),N=10G,内存占用64k多一点");
Console.ReadLine();
break;
}
}
}
public static void writeFile()
{
//写10000个文件，用来实验的；写一遍就可以了。
//腾讯不会那么傻把10G个数字存储到一个文件里
//应该存储到10000个文件，每个文件1000 000 （1M）个数字。
for (int x = 0; x < 10000; x++)
{
FileStream FileWriter = new FileStream(@"C:\" + x + ".txt", FileMode.OpenOrCreate);
System.Random rand = new Random();
for (int i = 0; i < 1000000; i++)
{
int tempInt = rand.Next(int.MinValue, int.MaxValue);
FileWriter.Write(System.BitConverter.GetBytes(tempInt), 0, 4);
}
FileWriter.Close();
}
Console.WriteLine("写文件完毕！");
}
}
superdullwolf
狼群
等 级：
发表于：2007-10-12 00:29:2348楼 得分:0
终于搞清楚了定义,又修改了下代码.
1，2，3，4，4，5，5，5，6，7，8，8，9，从小到大排好了顺序
一共是13个，其中5有3个，4和6有2个，其他都是1个
中位数，就是这些数据排列好了以后中间的那个数字，比如现在是13个，中间那个应该是第7个，所以就是5，那么如果有偶数个数据，那么就是中间两个数字的平均数，比如说18个数据，就应该是第9位和第10位相加除以2。
C# code
using System;
using System.IO;
class Program
{
static void Main(string[] args)
{
//这程序编译通过，但是我没运行，虽然复杂度是O(n)占用64k多一点内存。
//我可不想写那么多文件，还费我那么多时间去运行它。
//运行前先写文件；
writeFile();
double[] Arr = new double[65536];
//循环读文件10000个，10个G数字，每个文件读到结尾，复杂度是O(N) ,N=10G
for (int x = 0; x < 10000; x++)
{
string FileName = @"C:\" + x + ".txt";
FileStream FileReader = new FileStream(FileName, FileMode.Open);
//去读文件，每次读4个字节一个整数。
int index = 0;
while (index < 1000000 * 4)
{
byte[] tempByte = new byte[4];
index += FileReader.Read(tempByte, 0, 4);
int tempInt = System.BitConverter.ToInt32(tempByte, 0);
Arr[(tempInt - int.MinValue) / 65536]++;
}
FileReader.Close();
}
double MedianBarrel = 0;
int theBarrelIndex = 0;
//复杂度是O(m) ,m=65536
for (int i = 0; i < Arr.Length; i++)
{
MedianBarrel += Arr;
if (MedianBarrel >= 5000000000)
{
//找到中位数所在的桶的索引；找到就退出
theBarrelIndex = i;
break;
}
}
//中位数所在的桶的最小元素是theBarrel*65536，最大是(theBarrel+1)*65536落在里边有k个数字。
//K是中位数那个桶被砸中的次数，如果数字超过整数就不好玩了。
double K = Arr[theBarrelIndex];
Arr = new double[65536];
//去读文件，每次读4个字节一个整数。
//复杂度是O(N) ,N=10G
for (int x = 0; x < 10000; x++)
{
string FileName = @"C:\" + x + ".txt";
FileStream FileReader = new FileStream(FileName, FileMode.Open);
int index = 0;
while (index <= 1000000 * 4)
{
byte[] tempByte = new byte[4];
index += FileReader.Read(tempByte, 0, 4);
int tempInt = System.BitConverter.ToInt32(tempByte, 0);
Arr[tempInt - theBarrelIndex * 65536]++;
}
FileReader.Close();
}
//关键时刻到了
double Median = 0;//用double类型，因为真的可能被砸中超过整数范围次数。
int[] result= new int[2];
int j = 0;
//复杂度是O(m) ,m=65536中途找到了就退出。
for (int i = 0; i < 65536; i++)
{
Median += Arr + theBarrelIndex * 65536;
if (Median >= 5000000000)
{
//得到那该死的两个数字 ,再求平均数就是中位数了。
result[j] = i + theBarrelIndex * 65536;
j++;
if (j == 1)
{
break;
}
}
}
//根据中位数定义，由于输入的是10G，是偶数，所以得到两个数字再除2就是了。
Console.WriteLine((result[0] + result[1])/2);
Console.WriteLine("全部复杂度是O(N),N=10G,内存占用64k多一点");
Console.ReadLine();
}
public static void writeFile()
{
//写10000个文件，用来实验的；写一遍就可以了。
//腾讯不会那么傻把10G个数字存储到一个文件里
//应该存储到10000个文件，每个文件1000 000 （1M）个数字。
for (int x = 0; x < 10000; x++)
{
FileStream FileWriter = new FileStream(@"C:\" + x + ".txt", FileMode.OpenOrCreate);
System.Random rand = new Random();
for (int i = 0; i < 1000000; i++)
{
int tempInt = rand.Next(int.MinValue, int.MaxValue);
FileWriter.Write(System.BitConverter.GetBytes(tempInt), 0, 4);
}
FileWriter.Close();
}
Console.WriteLine("写文件完毕！");
}
}
religiose
月下摄魂曲
等 级：
发表于：2007-10-12 08:49:2849楼 得分:0
中位数 是不需要排序的， 大家翻翻初二的课本吧！~~~~~~~~~~~~~~~~~~~
sankt
短暂的总是浪漫,漫长总会不满,烧完美好青春换一个老伴.
等 级：
发表于：2007-10-12 09:23:1750楼 得分:0
楼上正解。
估计出题者也没有弄清楚中位数的定义
他的想法或许就是排序。
//===========
中位数：
简单来说就是
若数字的个数是奇数那么个数+1/2所对应的那个数就是中位数EG:2 5 6 8 7 4 9 中位数是：7+1/2=4 从左数的第4个就是了。
若数字的个数是偶数那么个数/2所对应的那个数+个数/2的商+1所对应的那个数的和的1/2就是这组数据的中位数EG：2 5 4 6 9 8 中位数是：6/2=3 6/2+1=4 也就是（4+6）/2就是中位数了
众数：
一般来说，一组数据中，出现次数最多的数就叫这组数据的众数。
例如：1，2，3，3，4的众数是3。
但是，如果有两个或两个以上个数出现次数都是最多的，那么这几个数都是这组数据的众数。
例如：1，2，2，3，3，4的众数是2和3。
还有，如果所有数据出现的次数都一样，那么这组数据没有众数。
例如：1，2，3，4，5没有众数。
ZelluX
ZelluX
等 级：
发表于：2007-10-12 11:13:1351楼 得分:0
以前在水源上看到过类似的讨论，见
http://www.blogjava.net/zellux/archive/2007/04/26/113743.html 发信人: xreborner (xreborner), 信区: Algorithm
标 题: Re: 请教腾讯笔试题
发信站: 饮水思源 (2007年04月24日11:23:07 星期二), 转信
……
一个整数假设是32位无符号数
第一次扫描把0~2^32-1分成2^16个区间，记录每个区间的整数数目
找出中位数具体所在区间65536*i~65536*(i+1)-1
第二次扫描则可找出具体中位数数值
wild_fox86116
修炼C/C++，网络安全
等 级：
发表于：2007-10-14 01:29:1652楼 得分:0
好东西学习了，谢谢各位
wild_fox86116
修炼C/C++，网络安全
等 级：
发表于：2007-10-14 01:35:3153楼 得分:0
我还是不明白中位数的定义
真的不用排序么？
我们初中没有学过
网上除了百度知道里面说不用排序外
其他的网页都显示要排序的
到底怎么回事？楼上的两位说明白点，你们的依据是什么？
shouhu13
守护
等 级：
发表于：2007-10-18 08:38:3454楼 得分:0
11楼的据说不错，只是不懂。
mark！
twice313
twice313
等 级：
发表于：2007-10-20 22:57:0355楼 得分:0
我面试的时候那家伙就问的我这个!
不过他说的是一亿个数
IT_worker
IT工人
等 级：
发表于：2007-10-21 19:39:1256楼 得分:0
打一个广告：
http://download.csdn.net/source/267630 上面的地址中可以下到我做的一个求解逻辑题目的程序，可以解出爱因斯坦难题、数独等问题。
蛮有意思的，有兴趣的下载运行试验一下。有什么问题和建议可以给我发邮件。
superdai
淨居天人
等 级：
发表于：2007-10-22 10:10:2057楼 得分:0
mark
guriyu
等 级：
发表于：2007-10-22 14:18:3058楼 得分:0
定义都搞不清楚,看来我们的水平还待提高,出题者也是如此.
khklsdfmg
7402-shy
等 级：
发表于：2007-10-23 07:57:5059楼 得分:0
學習
fonny0610
等 级：
发表于：2007-10-23 17:29:2060楼 得分:0
应该不用那么复杂。首先遍历文件一遍取所有数的平均数（可分段取平均再进一步求平均），再遍历一遍文件，依次比较取得的数与平均数的差，每次保留最小差及对应的数，最后该数即为所求。
liyips
liyips
等 级：
发表于：2007-10-23 22:12:5561楼 得分:0
用C#的越来越多了
liyips
liyips
等 级：
发表于：2007-10-23 22:27:5562楼 得分:0
终天看明白11楼的意思了,感谢OO;
fonny0610
等 级：
发表于：2007-10-24 16:07:2363楼 得分:0
11楼的算法太理想化，极端情况下，如果这10G个数都在一个段内（因为可能有重复的整数），这个算法就没有任何作用了。即使不是极端情况，这10G个数的分布也应该是不平均的。
yongguozhou
等 级：
发表于：2007-10-24 22:57:3564楼 得分:0
23楼的算法很好
p0303230
初来乍到
等 级：
发表于：2007-10-25 08:56:5065楼 得分:0
mark
superdiablo
等 级：
发表于：2007-10-25 13:12:5966楼 得分:0
同意11楼。
60楼不对，平均数不能作为求中位数的依据。其他试图用类似办法求中位数的应该也是错误的。
中位数是这样一个数：一半的数字比它小，一半的数字比它大。
下面一组数其中位数是0，但是其平均数是5，而且中间还有其他数字：
-1,-1,-1,-1,-1,0,1,1,1,1,56
如果你修改最后一个数字可以让平均数任意大，而且中位数不变。
zhuwuwei
光棍
等 级：
发表于：2007-10-29 17:53:3967楼 得分:0
10G个整数就有40G个字节，也就是说他文件大小40G？他整个数据库，让数据库自己排序不得了，还给你压缩。
Haimiao
noblesea
等 级：
发表于：2007-10-30 00:38:1868楼 得分:0
文件排序的问题。
将10G文件排序分成x个已经排序的文件
再就是合并文件的过程。
waterx
等 级：
发表于：2007-10-30 13:17:4469楼 得分:0
41楼的最好,只是算法不太通用,大家看41楼的吧.
baidu100
昨晚的确是我！
等 级：
发表于：2007-10-31 18:19:4470楼 得分:0
C# code
hrb133yqq
等 级：
发表于：2007-11-01 15:09:0071楼 得分:0
10*(2^1000)=
1071508607
1862673209
4842504906
0001810561
4048117055
3360744375
0388370351
05112493
6122493198
3788156958
5812759467
2917553146
8251871452
8569231404
3598457757
46985748
0393456777
4824230985
4210746050
6237114187
7954182153
0464749835
8194126739
87675591
6554394607
7062914571
1964776865
4216766042
9831652624
3868372056
680693760
309位
hrb133yqq
等 级：
发表于：2007-11-01 15:23:2572楼 得分:0
偶理解错误!
kendan
等 级：
发表于：2007-11-01 15:25:2173楼 得分:0
study
iwillalwaysloveyou
等 级：
发表于：2007-11-01 15:45:4874楼 得分:0
mathe,你的算法和我想的一模一样，连分的段数都一致。-____-!
iwillalwaysloveyou
等 级：
发表于：2007-11-01 15:51:3375楼 得分:0
请关注一下本人的问题：D
有好方法本人的分全送了。
http://topic.csdn.net/u/20071101/14/cba9fd07-8979-47dc-bc4a-fc9340e5bcc8.html zkbuchaladi
等 级：
发表于：2007-11-01 16:41:4376楼 得分:0
study
czc411
等 级：
发表于：2007-11-03 16:16:2977楼 得分:0
等候最佳解决方案
syy6
等 级：
发表于：2007-11-04 13:38:4378楼 得分:0
2007年11月4日
腾讯上海的校园招聘，又考了这个题目。
以前看过这道题目，但是也没多大印象。
mdzhao
读破书万卷
等 级：
发表于：2007-11-06 10:28:4979楼 得分:0
学习
D20080808
碎玉尓谙
等 级：
发表于：2007-11-07 15:22:4280楼 得分:0
Mark，慢慢看
Elysium
東鱗覀爫
等 级：
发表于：2007-11-08 11:50:1781楼 得分:0
中位数是需要排序的，如果不排序，从统计上来说中位数就没有意义
初中课本中即使有中位数概念没有指明排序，也应该是给出的一组排序后的数据，而对于初中生来说，解释排序算法略显高深
xkw365
kk
等 级：
发表于：2007-11-08 11:51:5582楼 得分:0
分成n段，分别计算出n段的中位数之和S,再取[S/n],似乎就可以
xkw365
kk
等 级：
发表于：2007-11-08 12:21:4283楼 得分:0
有必要知道这些整数的范围是多少？
xkw365
kk
等 级：
发表于：2007-11-08 14:21:3484楼 得分:0
把10G的分成5份，每份2G，分别求出它们的中位数，按大小排列m1、m2、m3、m4、m5；然后去掉m1对应的低半部分和m5对应的高半部分，就剩下8G了，重新求它的中位数，可以采用相同的方法....一直下去直到求到中位数
而对每份，已可以采用类似的方法求他们的中位数
xkw365
kk
等 级：
发表于：2007-11-08 14:23:1585楼 得分:0
以上m1 <=m2,m3,m4 <=m5
dchilli
Jorn_Yen
等 级：
发表于：2007-11-08 17:02:5786楼 得分:0
MARK
heixia108
heixia
等 级：
发表于：2007-11-11 02:08:2987楼 得分:0
mark
youngshuaishuai
等 级：
发表于：2007-11-13 14:16:3688楼 得分:0
只有学习的份。
需要努力
Eleve
没头脑&不高兴
等 级：
发表于：2007-11-13 17:08:1189楼 得分:0
学习学习！！！
edgeperson
对流血一周仍然不死的动物千万不能大意……
等 级：
发表于：2007-11-13 21:23:0090楼 得分:0
31楼```
排序`````??? -_-!!!
会不会冒泡泡冒到天都黑了```
mikster
等 级：
发表于：2007-11-14 14:08:0391楼 得分:0
84楼正解，不过在均匀分布的条件下，分段计数是不错的想法~~
Rico_J
Rico
等 级：
发表于：2007-11-14 19:23:1292楼 得分:0
文件y中的数据格式为：
A段 ¦B段 ¦
数据量：
2000000
要求：
1、将文件中的数据以A段为排序字段进行排序，并输出到文件A，形如：
4600xx001 ¦138xx001
4600xx002 ¦138xx001
4600xx003 ¦138xx001
2、将文件中的数据以B段为排序字段进行排序，并输出到文件B，形如：
4600xx001 ¦138xx001
4600xx001 ¦138xx002
4600xx001 ¦138xx003
3、需计算两次排序处理所需要的时间（如数据装载时间、排序时间）不能放进数据库排序，以毫秒为单位
有没有人知道方法?
raymondli
等 级：
发表于：2007-11-14 20:15:1593楼 得分:0
我连中位数都不知道是什么,整数占多少空间??N位,你们在哪学的呀,人才呀.
zhoulijian
jian
等 级：
发表于：2007-11-14 22:36:0894楼 得分:0
跟大哥们学习~~!
ntzhouhao
ntzhouhao
等 级：
发表于：2007-11-15 02:05:5495楼 得分:0
整数.....不就是一计数排序吗,只要这个整数不大于20000000000
xhappy
等 级：
发表于：2007-11-18 00:23:2496楼 得分:0
当时群硕软件 也出了类似的一道题 可惜我不会 郁闷。
jdz_ln
等 级：
发表于：2007-11-23 11:28:4697楼 得分:0
我的想法。
有10G个数。假设中间数为a，b 。则数据分为 5G-1，a，b，5G-1
那么中间数要满足：
a：①有5G个数大于等于他
②有5G-1个数小于等于他
b：③有5G个数小于等于他
④有5G-1个数大于等于他
a左边的数满足
⑤有5G+N（N> =1）个数大于等于他
b右边的数满足
⑥有5G+ N（N> =1）个数小于等于他
我的算法是，取文件第一个数为X，然后同后面的数依次比较
Ⅰ.当满足⑤时②变为有5G-2个数小于等于他
③变为有5G-1个数小于等于他
然后取下一个数为X
Ⅱ.当满足⑥时④变为有5G-2个数大于等于他
①变为有5G-1个数大于等于他
然后取下一个数为X
………
依次取数比较当有符合①②的就是a，有符合③④的就是b。
这样的考虑是我们只用考虑a，b的情况，对于a，b两边数的顺序完全可以不用考虑
还希望大家幚我把效率提高。
1
不用一次全拿来比较。我只要比X大或小的个数，那每次除了X，再拿几个数看内存，内存就够用了！o(∩_∩)o…哈哈
2
“有10G个数。假设中间数为a，b 。则数据分为 5G-1，a，b，5G-1”
的意思是 中间数处于排序后序列的位置 就是我们不用考虑前后各5G-1个数的顺序。
不是那样分组。
csl435
龙行天下
等 级：
发表于：2007-12-04 16:11:5498楼 得分:0
有意思呵呵 .
gming2003
DOTA is five
等 级：
发表于：2007-12-24 13:52:5899楼 得分:0
学习一下
