一道腾讯面试题

思考了个把小时，有一个思路：
这里不能贴图，详见
http://skzr-org.iteye.com/blog/631252
输入所有数据,返回第dataSize/2个值

-->分段读取数据-->分成N等分已经排好序的(保存每一段的最大，最小，中值，作为切分值点)

-->依次取N等分 使用切分值点切分追加到文件split(i)中 i表示第i个切分点

-->得到中间值所在的区间split(i) 好了现在回到了初始状态了，需要获取的是数据集split(i)的第(dataSize/2 - sum(i-1))个值;sum(i)=sum(i-1) + split(i).size

详细见图

随机采样可否？从这10G数据中随机取一些数，直到内存装不下为止，然后用经典的median算法求中位数。

这个复杂度是 O(n*lgn)
～～～～～～～～～～～～～～

你这没意义啊，排序算法就是O(n*lgn)。先用unix的sort命令排序，再取中间一行就行了。

我知道可能有更好的可能
但是。。。。
没知道更好的方法之前
我能想到的就这个方法了。

这东西跟硬件环境有关系哦 拿手机上的算法在小型机上跑 显然是不合理的

内存多大 磁盘I/O多大 cup处理性能如何

编辑下。。。有点问题

这个重点考的是外部排序的概念吧。只要是能进行外部排序的算法都可行。

这个思路差不多，定义多个连续整形范围的文件
整数范围是0 - 2^32 - 1，一共有4G种取值，映射到256M个区段
然后将文件一部分一部分的读，放入区段文件中... 

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

呵呵，想到一起去了。我也用的是你这个算法，其复杂度应该不会是 O(n*lgn)

     我们都知道求中位数的一般算法都是先排序，再求:中位数 = A[(n+1)/2](n=奇数)或(A[n/2]+A[(n/2)+1])/2(n=偶).这种前题是我们必须要先排序，但一排序我们的复杂度会为O(n*lgn)。我认为找中位数我们只关心的是中间那个数是多少，而没必要去把所有的数都重新排序。现借用你以上的思路简要说明一下我的方法，望大家仁者见仁，智者见智，不对之处，还望更正与完善。

      现假设有n个正整数（为了方便，先假定n为奇）那么中位数一定是第(n+1)/2个数，我们先取区间[0,100),[100,1000),[1000,+∞)；然后让程序跑第一遍，找出每个对应区间的频数，分别为:m1,m2,m3。

第一种情况： 
      if: m1>m2+m3 （或m1>=(n+1)/2）这是最理想的清况，那么中位数一定在[0,100)之间，再将区间分成[0,50)[50,100)两个区间的，同样找出对应的区间的频数 m11,m12。
          if: m11 > (n+1)/2 那么中位数一定在[0,50)之间，然后再递归,直到区间无法再以整数划分时(跨度为1)，其值就是中位数.这种情况下复杂度只与我们选择的区间跨度的2分到跨度为1的次数t有关O(t),且至少有(n+1)/2个与中位数相等的数(如:2,2,2,2,2,2,8的中位数)。否则在[50,100)之间。再将该区间划分成[50,75),[75,100)其对应的频数分别为m121,m122，
                 if: (m11+m121)>(n+1)/2(判断值取所有除去最后一个区间的其他频数之和) 那么中位数一定在[50,75)区间内，否则在[75,100)内，继续递归调用，至到区间不能再分隔。其复杂度仍为O(t).

第二种情况:
     if:m2>m1+m3(或m1>=(n+1)/2)其算法同第一种情况一样.（一开始就划分三个区间只是为了方便说明，其实也可以直接划两个区间）

第三种情况:
     if:m3>m1+m2(或m3>(n+1)/2)，其中位数落于)[1000,+∞),那么我们再将利用程序对其进行试探性划分，直至落在[x,+∞)区间的数为0时（可用x=1000q,q=10）进行等比划分。再对区间[1000,x]进行如上的区间无限划分进行中位值求值。这时的判断值我们应取除去第一个的所以其他区间的其他频数之和与中位数位置数(n+1)/2)做比较。其复杂度仍为O(t).
     由于时间关系未做临界值与负数的判定。