Find Median in super big array

求一个很大的数组的中位数(太大所以不能全放内存里)

Follow up: 如果求的是第k大呢?

这题好像用桶排序?不过主要思想是过几遍,每次统计个数。

譬如,要找到数组有100个数,但内存只能放10个。我们先把数字分成10组,1~10,11~20 ... 91 ~100。统计好了每个篮子里出现的次数。譬如我们总共有91个数,那么第46个数就是中位数,那么第46个落在哪个篮子里,我们就把那个篮子取出来。譬如落在21~30,我们把这个篮子又分10份,21,22 ... 30,然后再把数一遍每个数出现了多少次。通过减去前面有多少个数,我们就能知道哪个是中位数了。举个栗子:譬如我们有3个区间,21个数,【1,10】有4个数,【11,20】有8个数,【21, 30】有9个数。因为中位数是11,所以我们知道中位数落在【11,20】这个区间内。而且是在这个区间里的第7个数。然后把这个区间扩大成,11(2次)12(0次)13(0次)14(3次)15(1次)16(1次)17(0次)18(1次)19(0次)20(0次)那么我们知道16就是我们要找的数

Last updated