一道腾讯面试题

随机找到个数
把数据重排一下
大于这数的放左
小于这数的放右
少的部分变成一个箱的总个数其它不管

多的那边再生成两个箱

每次计算出来中值可能在哪个箱中
就拆哪个箱子

左右摆动直到中间的数组足够小。。。。

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

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

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

这个算法应该是最优的。
设映射空间为x，则第m个映射空间的映射大小是(MAXINT / x) * (m, m + 1)
第一次读入文件，但不记录数据，只记录数据在某个映射空间的数量，
经过第一次编历后，可以获得每个区间的统计数，
然后计算，获得中位数的区间。这是一次O(n)的处理。内存空间为常量

第二次处理，设置一个长度为x的投射空间，再一次读入文件，
把数据投入这个空间，同时做累计处理。第二次获得的精细值结合前面一次
的前后位置统计值进行校准，从而获得中位数。第二次处理也是O(n)的运算，内存同样是常量。

所以这是一个O(n)的运算，内存复杂度为常量。至少，题目得解。

一个tricky的东西是，在算法导论中有一个著名算法，求中位数。但难度比这个大很多，
原因是这个题目知道样本空间为有限的整数空间，所以直接投影可以解决所有问题。

b4腾讯。这样的题目，无聊时坐着想不难想到，但叫我在现场做题就要骂人了。

10G的整形大概有25亿个整形,想从里面找寻中位数,我有一个最多32n的方法

1.每个数对首位进行异或运算(不懂异或的不用看了)并计2个数量,分别代表了[-2^31~~-1]和[0~2^31-1]的数量,假定为15亿个正数(假定包括0)和10亿个负数,那么答案在[0~2^31-1]范围内

2.哪堆数量比较多,就记录首位数字a(0代表正数,因此a=0),第二遍历的时候就首先满足首位是刚才记录的a,然后再对第二位进行异或运算,并计2个数量,代表了[0~2^30-1]和[2^30~2^31-1]的数量,假定为10亿和5亿,那么答案在[2^30~2^31-1]范围内

3.跟第2步一样,除了首先满足的条件是首位和第2位是0和1(看不懂?整数01开头的整数就代表[2^30~2^31-1]的范围)

4.......

5.......

.......

为什么说是最多32次?因为整数是由32位组成的

为什么说是最多?因为一旦判断不出中位数在哪堆范围内,只需要再来一次,计算这两堆数比较小的堆最大数,和较大堆的最小数,加一下除以2,那就是中位数

到最后一次的话,满足前31位相同,那么就只剩2个数,只要两个数都存在,加一下除以2就是答案,不然??就是那个只存在的数

PS:这里有一点要注意,如果一开始计数时,有一堆超过了整数大小就会导致程序不准确,应该用long型计数

(全思路完结)

10G的整形大概有25亿个整形,想从里面找寻中位数,我有一个最多32n的方法

1.每个数对首位进行异或运算(不懂异或的不用看了)并计2个数量,分别代表了[-2^31~~-1]和[0~2^31-1]的数量,假定为15亿个正数(假定包括0)和10亿个负数,那么答案在[0~2^31-1]范围内

2.哪堆数量比较多,就记录首位数字a(0代表正数,因此a=0),第二遍历的时候就首先满足首位是刚才记录的a,然后再对第二位进行异或运算,并计2个数量,代表了[0~2^30-1]和[2^30~2^31-1]的数量,假定为10亿和5亿,那么答案在[2^30~2^31-1]范围内

3.跟第2步一样,除了首先满足的条件是首位和第2位是0和1(看不懂?整数01开头的整数就代表[2^30~2^31-1]的范围)

4.......

5.......

.......

为什么说是最多32次?因为整数是由32位组成的

为什么说是最多?因为一旦判断不出中位数在哪堆范围内,只需要再来一次,计算这两堆数比较小的堆最大数,和较大堆的最小数,加一下除以2,那就是中位数

到最后一次的话,满足前31位相同,那么就只剩2个数,只要两个数都存在,加一下除以2就是答案,不然??就是那个只存在的数

PS:这里有一点要注意,如果一开始计数时,有一堆超过了整数大小就会导致程序不准确,应该用long型计数

(全思路完结)

能不能画下图啊，看不明白你说什么？

  我不善于画这类图，如果是草图还行

其实我想这个问题我与lyw985等几位朋友讨论得很清楚了，你可以将我们的贴子连起来读，后面都具有详细的描述。
总体的思路就是说查找中位数是个很特别的算法，他并不需要排序，只需要找出那些比它大，那些比它小就行了，总体说来，时间复杂度为O(n)的
1-100之间为什么55.5是中位数，并不需要将1-100全部排好序并求出它是最中间的。
而是因为1-10间有10位数，11-20有10位数,,,91-100也有10位数。
你能得到一个分布为10,10,...,10的数组。
中位数在哪里，有了这个分布数组，我想找起来是件非常简单的事了。

有5个数，{1, 2, 100, 9999, 10000}，请问中位数是什么？