记忆碎片

前天在网上看到一个题目，说的是求中位数，但是这个中位数，不是我们所讨论的那样简单。看题目如下：

在32位机器中，int占4字节，存在文件中的4T个数中找出第2T大的数，内存只有2G。请列出解法。

这个题目，其中有个问题有些复杂，不过肯定是有解法的。其中，4T个数，每个数占用4个字节，那么就应该是16TB的内存才能存的下，这样算来，是不能在内存里面处理全部数据了，其实如果真的想不到好的办法，可以用最朴素(也可以说是最笨)的方法，对文件进行外排(归并),就可以求出来了。

看到这个问题，我首先想的到的是用分治法。分治是肯定可以解决这个问题的。

解法1 分治法

依次读取数据，按每一个数据的最高位分别写到文件(bit_32_1、bit_32_0)里面去，并同时记录最高位为1的个数，这样就可以找到第2T个数是在bit_32_1 or bit_32_0中，依次递归下去，就能找到第2T个数是多少。

我们考虑到，数据比较大，而且是放到文件中的，如果用这种方法，就多次(<=32次)读取文件，时间复杂度应该是O(32*N)。有没有更好的办法呢？答案肯定是有的。我们在群里讨论了这个问题。提出了一个基于计数的思想。

解法2 计数分治

既然全部的数据在内存中存放不下，那么我就考虑存放两个计数桶，分别求出第2T个数的高16位和低16位，这样就不把问题解决了吗。而且使用内存较小。64K x 8 x 2 = 1MBytes下面是我写的一个伪代码，可能有些疏忽的地方，但是思想肯定是对的啦！呵呵

long long High[1<<16];
long long Low[1<<16];
long long x = 0 , i = 0;
int  Number = 0 ;
while(x<= 4T)
{
     data = read();
     High[x>>16]++;//记录高16位–yqshare
     Low[x&0xFFFF]++;  //记录低16位–yqshare
}
x = 0 ;
while(x>=2T)
{
     x += High[i++];//累计大小–yqshare
}
Number = (i–)<<16 ;
x = 0 ;
i = 0 ;
while(x>=2T)
{
     x += Low[i++];
}
Number |= (i–)&0xFFFF;//添加上低16位–yqshare

上面是错误的解法，Harvey指出来以后，我思考了下，发现自己图略了一个问题。然后修改了一下算法。

long long High[1<<16] = {0} ;
long long Low[1<<16]= {0} ;
long long x = 0 , i = 0 ,HighCount;
int  Number = 0 ;
int HighNumber , LowNumber;;
while(x<= 4T)
{
   data = read();
   High[data>>16]++;//记录高16位–yqshare
   x++;
}
x = 0 ;
i = 0;
while(x>=2T)
{
   x += High[i++];//累计大小–yqshare
}
HighNumber = (–i)<<16 ;
HighCount = i ;
while(HighCount>=High[i])
{
   i++ ;//计算出小于2T数的个数–yqshare
}

//这里可以用堆的思想，也可以用桶的思想。
x = 0 ;
while(x<= 4T)
{
   data = read();
   if(data&0XFFFF0000 == HighNumber)
      Low[data&0XFFFF]++;//记录高16位为HighNumber的数的低16位–yqshare
   x++;
}

x = i ;
while(x>=2T)
{
   x += Low[i++]; //累计大小–yqshare
}

LowNumber = (–i)&0xFFFF;//添加上低16位–yqshare

Number = HighNumber | LowNumber ;

这样就可以求出该数了。