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


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

 

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

 

#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来记录一个信息也是一个重要的编程技巧。希望读者朋友们多多体会和应用。



看文字不过瘾?点击我,进入腾讯课堂视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注