一道腾讯面试题

1、遍历一遍数据，找出最大值和最小值。
2、(最大值+最小值)/2 得中间值。
3、再遍历一遍数据，找出与中间值差值最小的数。

1、遍历一遍数据，找出最大值和最小值。
2、(最大值+最小值)/2 得中间值。
3、再遍历一遍数据，找出与中间值差值最小的数。

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

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

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

@zhaoyifei

例如：a = {1,2,3,4,5,6,99}

按照你的算法，。。。。

java.util.BitSet 可以搞定本题

1、遍历一遍数据，找出最大值和最小值。
2、(最大值+最小值)/2 得中间值。
3、再遍历一遍数据，找出与中间值差值最小的数。

这个是最佳方案。

1、取 16*1024 个数，生成一个 TreeMap 。取得最大值 max 和最小值 min。
2、构造一个1024个元素的计数数组 T[i]，对最初的 1024 个数按区间计数；
对 min 和 max 进行 1024 个等分,各等分值为 N[i]。

当数据 N[a]<data<=N[a+1] 时， T[a]++；