一道腾讯面试题

这个简单,只需要从头读取然后插入另一个文件,维持中间位数即可,几行代码搞定!

这位仁兄，你太牛了，能否把你的几行代码贴出来让大家共同拜读一下。这里是10G，你拷贝一个还算可行，如果是100G或更大呢，你安排怎么处理的?还有你是怎么在另一个文件中去维持中位数是哪个，是否可以给出你的思路?

这个题目有挑战性

哈哈,如果这个问题再加一个条件:只有1M的内存怎么办呢?


首先数据的表示方法要变化一下,用向量来表示整数集合,比如集合{1,3,4,5}可以表示为
010111

第一步,初始化所有位为0,n为多少位,如果位太多可以以文件的形式,文件的第几位....
for [0,n)
   bit[n] = 0;
第二步,读取源文件,把相应的位置1
for each i in input file
   bit[i] = 1;
第三步,输出 , 都是排好序的
for [0,n)
   if(bit[i] == 1)
      write i on output file

如果有重复数据要处理一下,一样存在两外一个文件里,第几位好多少个,输出的时候判断一下即可

貌似应该差不多了

     首先数据的表示方法要变化一下,用向量来表示整数集合,比如集合{1,3,4,5}可以表示为
010111 ——这可是让我大开眼界了

若有哪位高手能看懂，还烦指教。
 

这个我看过，对算法不太了解，模模糊糊的好像没看懂。。。

对这个问题，我说说自己的想法，个人感觉有以下难点：
问题有个前提，是数据量够大，超出了内存的限制，所以通常解决办法就我知道通常有两个：使用索引和分段处理。
使用索引是对每个数据进行处理，并记录引用地址和处理结果。问题的前提是数据为长整型，所以使用索引一样会带来巨大的内存消耗。
分段处理是将数据划分成多个模块，批次进行处理，但是通常的解决办法中对每个段中的数据处理结果和中位数等都不会影响到整体的结果。

我的思路是，求解中位数，是不一定要排序的，只要比较出中位数所在位置就好了。
我的办法很简单，其实跟链接里的办法是差不多的（或许就是一样的）。
1.设置一个数组，大小为2的整数倍，如1024x1024。
2.遍历10G数据，先将数据按照大小分类，最简单的办法就是将数据整体右移20位，得到的结果为n，那么在数组的n位上进行加1的操作。
  完成第一次遍历后，就会得到一个大小为n的，记录了不同区间范围的数据的个数的数组（很拗口！）。
3.我们对该数组进行分析，依次判断首尾个数，并依次比较，如果小于另一个数就取离其最近的一个数继续比较。打个比方,第0位上个数为10，第1024x1024位上个数为11，那么1024x1024上个数减为1，而首部到第1位上继续取值比较。。一直下去，直接比较到中间的某两个区间（也可能是一个区间）。。
4.一个区间就不用说了，重新遍历10G数据，找出符合该区间的数据,排序求出中位数即可。
5.如果是两个区间，就是多了一个判断的过程，找出个数比较大的区间即行遍历，排序。并去掉其中与另一个区间中相同个数的数据。，再求出中位数即可。
这样，通常情况下，通过分组后的数据大约需要使用10亿/100W的内存空间，，数组自己占用1024x1024x32b的内存空间。。这种方式比索引的效果应该好很多。。

我明白他的意思，可能是建立个足够长的BIT数组,每位代表1个数字在文件中是否存在,比如"集合{1,3,4,5}可以表示为
010111 " 这里0不在集合中,1在集合中,2不在集合中,3、4、5在集合中。遍历1遍文件既可得到所有数字的集合，再采用特定算法取到数组中所有1的中间位置（然后循环BIT数组到:数组和除2个1的位置），再通过数组下标得到这个值。
这个思路是挺独特的，效率也很高。呵呵

这个思路牛B。只要建一个byte[int.MAX]的数组就行了。读取一遍文件，存在的数位置1，仍然再计算中间的数。又快又省资源。

这个byte[]你知道是多大吗？比那个文件小不了多少

第一次读出最大最小数，算出中间值，第二次找出距离中间值最近的数。2n就可以了。当然读的时候也不耗费内存，只需要存最大最小，中间值，中位数就好了。