一道腾讯面试题

。。我只是没有找出你为什么选择5亿的原因，是根据去掉的那10亿负数么。。

宾果，可能我没说清楚。。。Sorry

你的算法我也看过，是非常不错的算法。

唯一不足的地方在于：必须要考虑到内存的问题

由于你的分割量比较少，1024*1024一般不会导致内存溢出的问题

总结来说，你的算法复杂度是O(n)，
而且也充分运用了内存，是我见到的最好的算法了吧

请问是这个思路么？

在第一遍遍历的时候，知道正数个数，知道负数个数，当然就会知道总共有多少数据了

我的算法需要每次都遍历数据，因为并没有储存任何的数据，只是记录了某一范围的数的个数而已

呵呵，我也基本是这思路。但有个问题，没想好如何解决：如果数据是 long 型的。数据分布范围可能极大。
2 的 64 次方啊。如果是 double 型就更可怕了。

我的问题就是，
1、如果数据分布很广，内存可能无法处理区间的计数。嗯，这种可能性应该很小。
2、可能在一个区间里集中了大部分数据。这样，可能需要多次扫描才能解决问题。

所以，我在想，有没有动态分区的算法，可以只扫描两次就得到中位数。第一次获取到足够小的区间，里面包含的数据个数足够少。第二次对该区间的数据排序，得到中位数。

是的，你的这个问题其实我也早已经注意到了。在我认为，这两个问题其实是一个问题，就是当区间里的数太多太大而无法一次性地判断出来。。
这里我能想到的办法还真就是再次扫描，，因为作为设定区间的数组必须要符合一定的内存开销，如果你有足够大的内存，那么当然设定一个2^64位的数组来，那么就能一次性的判断出所有内容了；同样，那怕你的内存再小，只要能设定2个数组，那么也是能够通过无数次扫描来判断出中位数在那一个区间的。
当数据类型为long类型时，那么设定一个符合内存限定的数组，就是最为关键的了，因为判定中位数本身是不消耗内存的，大部分内存消耗都是花费在设定的这个数组上。。或许，1024x1024就是一个不错的选择，，因为100万数据本身的排序很快，当为long类型时，再判断下一个1024x1024即右移40位，那么long类型通常也最多只要遍历4次就够了了。
如果一个区间集中了大部分数据，我想，这个解决办法也还是多次扫描了，判断下一个1024的数据，即右移30位，那么就可以更准确地找到中位数所在了。
总体上来说，我认为遍历的次数应当不至于太大才对。在分区划分完毕后，对该区的次数进行一个判断，如果其中个数能够被内存一口气加载进来，那么也就无所谓再细化扫描了；反之，如果该分区中包含中位数，且其中个数超过了内存限制，那么就继续细化。。。并以此类推。。。。

至于有无更好的办法，希望有人能够提点指教！

第一次IO：
1、打开文件，读入合适大不的数据至内存（如1G），降序排序后输出至硬盘文件a1
2、如果原始数据是10G，那输出文件a1-->a10
3、并获取整数总共有N个

第二次IO：
同时打开10个文件，归并排序，直至读出中位数统计学定义。

这位仁兄，通常情况下，题目要我们做什么，我们就做什么，

不能做多，做多就意味着浪费了（不管是时间还是什么东西）

您的算法，都能把25亿的值排个序了

大家似乎对这个方法讨论很激烈呀，我也掺和一下：

首先谈谈数据规模：

10G整形，假设每个整形4bytes，那么有多少个整数呢？  10*1024*1024*256=2,684,354,560  约26亿

一个4bytes无符号整数最大是多少呢？ 2^32-1=4294967295。谁也不知道这个10G文件里面有什么，如果有1，也有4294967295。按照{1,3,4,5}可以表示为010111一种想法，请问是不是需要bit[4,294,967,295]呢，也就是需要4,294,967,295bit=4G。

另外，“如果有重复数据要处理一下,一样存在另外一个文件里,第几位好多少个,输出的时候判断一下即可。”另外一个文件要大呀，每一位统计多少个。现在有4,294,967,295位，约26亿的整数，最大的统计值也就是2,684,354,560，需要
一个整形吧(4个字节)。每一位用一个整形来记录相同的数，那么要4,294,967,295*4bytes=128G。

好吗，随口一说132G没了。不知道为什么位图的思想那么根深蒂固。

一句话，上面的方法我非常不赞成：



我大致想了一下，可能不很全面。既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序可不可以呢？？

一个整数4bytes，可以每8位作为一个关键字。

第一步:把10G整数每2G读入一次内存，然后一次遍历这536,870,912个数据。每个数据用位运算">>"取出最高8位(31-24)。这8bits(0-255)最多表示255个桶，那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中，同时在内存中统计每个桶内数据的数量，自然这个数量只需要255个整形空间即可。

第一步的代价：(1) 10G数据依次读入内存的IO代价(这个是无法避免的，CPU不能直接在磁盘上运算)。(2)在内存中遍历536,870,912个数据，这是一个O(n)的线性时间复杂度。(3)把255个桶写会到255个磁盘文件空间中，这个代价是额外的，也就是多付出一倍的10G数据转移的时间。

第二步：根据内存中255个桶内的数量，计算中位数在第几个桶中。很显然，2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加，发现少于1,342,177,280，把第128个桶数据量加上，大于1,342,177,280。说明，中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(平均而言，每个文件的大小估计在10G/255=40M左右，当然也不一定，但是超过2G的可能性很小)。

第二步的代价：(1)循环计算255个桶中的数据量累加，需要O(M)的代价，其中m<255。(2)读入一个大概80M左右文件大小的IO代价。

注意，变态的情况下，这个需要读入的第128号文件仍然大于2G，那么整个读入仍然可以按照第一步分批来进行读取。

第三步：继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同，也是255个桶。

第四步：一直下去，直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。


整个过程的时间代价主要消耗在 第一步的额外一次10G数据分255个文件写回磁盘上。一般而言，如果第二步内存可以容纳下存在中位数的某一个文件的话，直接快排就可以了。关于快排的效率，可以看看我博客中的数据《http://hxraid.iteye.com/blog/646760》。3.06GHZ主频的CPU快排150W个整数，大概400ms左右。


这个方法可能不是最快的，但在一台现代计算机上，绝对是可行的。