在线咨询
有事点这里
有事点这里
看不懂这篇文章?联系我们
("麦洛克菲"长期致力于内核安全的推广与普及,我们更专业!)
求职QQ群:223902435。讨论各种求职笔试面试问题
作者:admin 时间:2015-10-31
标题:在一个文件中有 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来记录一个信息也是一个重要的编程技巧。希望读者朋友们多多体会和应用。