---

在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2GB。

 

分析：假设每个整数用一个bit表示，10G个整数就需要10G个bit=10G/8=1.25G个字节 < 2GB的内存限制。所以在内存中定义一个1.25GB的大数组，定义一个整数total = 0，然后从文件中读入整数，每读入一个整数就把大数组中相应bit位置为1，同时total加1，这样所有的整数读完以后，total就是大数组中bit为1的个数，也就是10G个数字中去重的数字个数。完成数组的初始化后，遍历这个大数组，第total/2个bit为1的数就是要求的中位数。

 

#define MAX_INDEX 1.25*1024*1024*1024

 

int findmidint()

{

     char a[MAX_INDEX];

     long value = 0;

     long total = 0;

     long index = 0;

 

     for(int i = 0; i < MAX_INDEX; i++)

     {

         a[i] = 0;

     }

 

     while ((value = GetANumFromFile()) != EOF)

     {

         if (!(a[value >> 3] & (1 << (value & 7)))

         {

              total++;

              ......

         }

     }

 

     for (int i = 0; i < MAX_INDEX * 8; i++)

     {

         if (......)

         {

              index++;

              if (index == total/2)

                  return i;

         }

     }

     return 0;

}

注意：用一个整数作为数组的下标并对这个元素赋值为0或者1来记录这个整数是否存在是一个重要的编程技巧。用一个Byte的每个bit来记录一个信息也是一个重要的编程技巧。希望读者朋友们多多体会和应用。