算法,求1亿个数的中位数

内存只能容纳100W个数,现在有1亿数,混序,然后求这一亿个数的中位数,中位数(就是一个有序数组的中间数字,数组长度为偶数就是两个,奇数则只有一个)
我想了半天最后只想出一个超没效率的方法,所以请各位大虾能够指点一下.

45 个解决方案

#1

你什么内存啊，
1亿个数字也就几百MB而已啊。。。

#2

内存只能容纳100W个数  这个只能算是个限制条件吧`~

#3

看来是结贴率过低

#4

是不是说要先排序，然后找出中间的那个数或中间的那两个数
数字有1亿个，太多了，排序算法或许可以有归并算法
学了太久了，也不知道是不是，回去想想后再来看看

#5

1亿个数字 没有那么夸张把

#6

楼主的方法是什么？

#7

顶下

#8

如果100w个数是个规定，想法应该类似文件的对路归并排序了。。

#9

不明白，顶一下。。

#10

外排，然后取第五千万和五千万零一的数。

#11

分块+递归

#12

楼主去参考下“五分化中项的中项”快速选择算法

#13

留意

#14

能实现 只是分块存储 排序算法没什么好的意见
但是楼主有什么算法没？

#15

先任意取一个数，然后把小于这个数的放到一个文件，大于这个数的放到另一个文件。根据两个文件的记录数判断，再取下一步。同样也是把小的放在一个里面，大的放到另一个。直到两个文件的记录数相等或者差一个

#16

如果是整数的话，这种可以利用位图的方法来做。
先把这1亿个数加载到内存里,对应数的bit位置1，这就相当于已经把这1亿个数排好序了，找中位数就很容易了。

#17

楼上的方法真好

#18

可以借鉴一下以下方法的：

有1亿个浮点数，请找出其中最大的10000个。提示：假设每个浮点数占4个字节，1亿个浮点数就要站到相当大的空间，因此不能一次将全部读入内存进行排序。

　　~~~~~~~~~~~~~

　　既然不可以一次读入内存, 那可以这么试试:

　　方法1: 读出100w个数据, 找出最大的1w个, 如果这100w数据选择够理想, 那么以这1w个数据里面最小的为基准, 可以过滤掉1亿数据里面99%的数据, 最后就再一次在剩下的100w(1%)里面找出最大的1w个咯~~

　　方法2: 分块, 比如100w一个块, 找出最大1w个, 一次下来就剩下100w数据需要找出1w个了.（注意消重，这剩下的100w个数据应该是互不相同的。即每找出一个块里最大的1w个，就应该hash存储。下一个块中若出现了已存储的数据，则不计在此块的top 1w里，这样才能保证最终剩下的100w里面寻找top 1w就接近1亿里面的top 1w。想想：如果每个块的top 1w都基本是重复的，不消重的话，最终的结果有可能就少于1w个。）

　　对于上面提到的找出100w个数据里面最大的1w个, 说起来比较罗嗦, 还是说说找到第1w个大的数字的方法:

　　用快速排序的方法, 分2堆, 如果大的那堆个数N大于1w个, 继续对大堆快速排序一次分成2堆, 如果大堆个数N小于1w, 就在小的那堆里面快速排序一次, 找第10000-N大的数字; 递归以上过程, 就可以找到第1w大的数. 据说也是STL的search_n()的方法;（更好的一种类似的方法是将这些数以5个为一组，每组通过插入排序找出其中位数，再找出其中位数的中位数，依次递归，找出最终一个中位数x，然后按照x对序列进行快排，且设x是序列的第k大的数，如果要找的是第i大的数，则比较k与i的关系，如果相等，直接返回x，否则如果k>i，则在小的那堆里面继续按照这种方式快排，如果k<i，则在大堆里面找第i-k大的数。）

　　参考上面的找出第1w大数字, 相信楼主就可以类似的方法找出前1w大数字了.

#19

真的很感谢有这么多人回答，我的思路就是基本上排序+分块，
首先1亿个数我分成了200块，每块50W个，对每个块进行多路归并排序（这里不考虑快速排序，相对来说比较低率，不稳定），
排序好后存储在硬盘文件。
我写了下，大约是15S左右，
然后在用一个两维数组记录这200组数据中的最大和最小值，然后把这200个中位数的平均数求出来，其实没有别的目的
（目的是为了找一个适合的中位数偏移点，因为这个平均数不一定就是1亿个数的，可以叫做先猜一个机率最大的吧）
如果我们这么时候求得的平均数是N
然后就是一个超级土的试探法了，
建立一个偏差数组left[5][200],right[5][200],主要是用来保存N这个数在每个块里面小于N和大于N 5个的数，用来在后面读取
1。从文件里一个一个读取排序好的块，顺便把left,right两数组填充，找出<=N的数所在的index,最后把这些index相加为sum，看sum是否==1亿/2-1
如果相等了，那证明这个数就是中位数了，
2.如果小于
就又从left[0][200]里取最大的一个值，把left[0]排序一下，这样肯定是最接近N的，然后重复1，但是不改变left,right，看是否是中位数，
如果sum继续小于,那么继续2，但是要取left[1][200]最大了,如果sum这时候大于了，证明中位数肯定存在于left[0][200]其中的一个了，
这时候就锁定了，在left[0]用折半找按上面方法计算sum找中位数，
3。如果大于，和2步骤就是相反的。

这个算法虽然可以找到相关的值，但是在从文件重复读块加载到内存方面不知道读取了多少次，效率肯定不是一般的差，想了一两天，没思路了，哎。

#20

up 16楼
不过需要先找出所有数据中最大的那个数。

#21

引用 20 楼 adventurelw 的回复:

up 16楼 
不过需要先找出所有数据中最大的那个数。

用位向量 100W的存储 就算每个数字都存了double 最后也只能存64*100W啊  不够1亿的啊

#22

引用 16 楼 donkey301 的回复:

如果是整数的话，这种可以利用位图的方法来做。 
先把这1亿个数加载到内存里,对应数的bit位置1，这就相当于已经把这1亿个数排好序了，找中位数就很容易了。

我算是服了你了！

#23

貌似求中位数不需要排序``` 算法导论 109 有 期望为0(n) 的选择， 112 页 有  最坏情况 是 0(n) 的选择，楼主应该可以参考下这里

#24

引用 22 楼 amossavez 的回复:

引用 16 楼 donkey301 的回复:
如果是整数的话，这种可以利用位图的方法来做。 
先把这1亿个数加载到内存里,对应数的bit位置1，这就相当于已经把这1亿个数排好序了，找中位数就很容易了。 


我算是服了你了！

我也觉得位图法不错。

#25

引用 16 楼 donkey301 的回复:

如果是整数的话，这种可以利用位图的方法来做。 
先把这1亿个数加载到内存里,对应数的bit位置1，这就相当于已经把这1亿个数排好序了，找中位数就很容易了。

楼主说了，只能放100W个数，如何将1亿个数存入内存啊？

而且，即便用一个比特表示的话也要1亿个比特，这也需要1250万个字节，仍然很难满足内存容量限制要求。

#26

学习了。

#27

o(n)
不停的用一个数去判断比这个数大的有多少
在分情况去判断左边和右边的数

#28

多路归并+外排可以解决。
但是效率不怎么样。

#29

本来如果不是内存不足的花，改进的快排，找中位数还是很有效率的。

#30

引用 16 楼 donkey301 的回复:

如果是整数的话，这种可以利用位图的方法来做。
 先把这1亿个数加载到内存里,对应数的bit位置1，这就相当于已经把这1亿个数排好序了，找中位数就很容易了。

这需要看是什么数据，有两点是不可以用位图的。
第一，有重复数据，如果有重复数据，
第二，不知道最大数是多少，位图不是根据数据多少分配大小，而是最大的数。

还有一点，就是在分配bitmap的时候要注意大端小端的问题，详细资料可参考《编程珠玑》

#31

引用 25 楼 zenny_chen 的回复:

引用 16 楼 donkey301 的回复:
 如果是整数的话，这种可以利用位图的方法来做。
 先把这1亿个数加载到内存里,对应数的bit位置1，这就相当于已经把这1亿个数排好序了，找中位数就很容易了。


 楼主说了，只能放100W个数，如何将1亿个数存入内存啊？

 而且，即便用一个比特表示的话也要1亿个比特，这也需要1250万个字节，仍然很难满足内存容量限制要求。

恩,没考虑清楚,那就先把中位数定位到一个100w长度的范围内,具体就是:
设内存最大值是M,
那空间可以分为[0,M],[M,2M],[2M,3M]....
把1亿个数每个除M求出落在上述各个范围内的个数.
这时也就知道中位数应该在哪个范围了.而且知道应该取第几个bit为1的数.

#32

引用 16 楼 donkey301 的回复:

如果是整数的话，这种可以利用位图的方法来做。
 先把这1亿个数加载到内存里,对应数的bit位置1，这就相当于已经把这1亿个数排好序了，找中位数就很容易了。

中位数又没说不能重复，BIT置1只能说明存在那个数，又不能统计那个数有多少个。

#33

顶一下！！！

#34

数据这么多，应该是文件操作了吧

#35

求中位数就是排序嘛  你们在研究什么呢？

#36

mark

#37

太失望了，唉，有谁可以介绍一个搞算法的论坛，

#38

弱弱的问一下，不知道老师给你的题目中有没有列出1亿个数来？单是输入1亿个数都要好长好长一段岁月！

#39

因为你不知道每个整数出现的次数，位图法在这里并不合适

#40

内存只能容纳100W个数,
现在有1亿数,混序,
然后求这一亿个数的中位数,
中位数(就是一个有序数组的中间数字,数组长度为偶数就是两个,奇数则只有一个)

/*****************************************************************************/
/* this program should find out the median(s) in N(logN)/(logB) no matter there
/* is duplicated data or not.
/*
/* with memory limitation: 4MB memory available.
/* I would like to express the idea with code.
/* here is just the pseudocode with out any optimization for easy understanding.
/* 
/* maybe, there is no need to check sum == N/2 or N/2+1, but this will get the 
/* median(s) as soon as possible with out more recursive invoking.
/*
/* sorry for any logical problem. please let me know if you found any.
/*****************************************************************************/


int N = 100000000;// total data number is N
int B = 1000000;  // number of buckets.
int min, max;
scan data from 0 to N-1 get min and max; // O(N);

void find_median(int num=0, int min, int max)
{
	if(min == max) {
		if(N%2) {
			print medians are min and max;
		}
		else print median is min; // show you the result
		return; // exit
	}

	/* count all the data in O(N)*/
	int m = max-min > B ? (max-min) / B : 1;
	int cnt[B] = {0}; // count the data read.
	while(!EOF) {
		int data = read_data()-min;
		if(data >= min && data <= max) cnt[data/m]++;
	}

	int sum = num, median_1, median_2, i = 0;
	while(sum < N/2) sum += cnt[i++];
	i--; // median is in the range of [i*m, (i+1)*m-1]

	/* get median(s) when sum is N/2 */
	if(sum == N/2) {
		if(N%2) { // N is even and there are two medians.
			median_1 = (i+2)*m-1;
			median_2 = i*m;
			while(!EOF) {
				int data = read_data()-min;
				if(data/m == i) {
					median_2 = (data > median_2 ? data : median_2);
				}
				if(data/m == i+1) {
					median_1 = (data < median_1 ? data : median_1);
				}
			}
			pintf medians are median_1 and median_2;
			return;
		}
	}
	else { // N is an odd number and there is one median.
		median_1 = (i+2)*m-1;
		while(!EOF) {
			int data = read_data();
			if(data/m == i+1) median_1 = (data < median_1 ? data : median_1);
		}
		print median is median_1;
		return;
	}

	/* get median(s) when sum is N/2+1 */
	if(sum == N/2+1) {
		if(N%2) { // N is even and there are two medians.
			median_1 = i*m;
			median_2 = i*m;
			while(!EOF) {
				int data = read_data();
				if(data/m == i) {
					median_1 = max;
					median_2 = (data > median_2 ? data : median_2);
				}
			}
			pintf medians are median_1 and median_2;
			return;
		}
	}
	else {
		median_2 = i*m; // get (N/2+1)th data.
		while(!EOF) {
			int data = read_data();
			if(data/m == i) median_2 = (data > median_2 ? data : median_2);
		}
		print median is median_2;
		return;
	}

	/* recursively to find out the median(s) */
	min = (i+1)*m-1;
	max = i*m;
	// get min and max for next processing
	while(!EOF) 
	{
		int data = read_data()-min;
		if(data/m == i)
		{
			min = (data < min ? data : min);
			max = (data > max ? data : max);
		}
	}
	find(min, max);
}

#41

last line:
find(min, max); ==> find_median(sum, min, max);

#42

引用 41 楼 jonsenelizee 的回复:

last line:
find(min, max); ==> find_median(sum, min, max);

这个算法不错!!!
顶

#43

找中位数并不一定需要排序吧，其实通过统计counting的办法就可以实现。

这里只使用M个桶，每个桶初始化数字为0，这里事先需要知道1亿数据的值域，然后将这个值域均分到M个桶上，每个桶分别代表某段值域上的数据个数，另外，对M个桶，再分别建立M个空文件。

然后读一遍原始数据，每次对每一个对应值域的桶+1，并讲那个数据追加到对应那个桶的文件中，这样就得到了每段值域上的数据个数，并分类到了M个文件中，由此可以判断中位数在哪个桶里。这就完成了一次迭代，那么下一次迭代就对中位数所在桶对应的文件进行操作，依次类推，直到文件里数据少于M，用M个桶过一遍就得到了中位数。

如果有N个数据，N很大，每次迭代使用M个桶，那么迭代次数k就等于log m N，即以M为底数的N的对数。这种办法的文件写入次数、数字比较次数、内存写入（赋值）次数均为：(M^(k+1)-1)/(M-1) * ([logM]+1)，这里[]表示向下取整，log以2为底数，算法复杂度为O(N/k*logN)，这里log以2为底。

那么取多少个桶最快呢？根据O(N/k*logN)的复杂度，要是该值尽量小，就要使k值尽量大，即：使M值尽量小（因为M^k=N）,M最小只能取2，因为1个桶是无法迭代的，只能最少2个桶（到此颇有二分法的意味）。这时：可以使时间复杂度降到logN，相当低了吧～

#44

另外，如果你觉得在N个大数据之外，再存N个大数据太耗费文件系统空间，也可以不要那些对每个哈希桶的新文件，但是这样每次迭代，就要针对长度始终为N的原始数据读取比较了，这时文件空间耗费和文件写入次数均降到了0，而比较次数会上升至N([log2 N]+1)logm N，这里第一个log以2为底，第二个log以M为底，其复杂度为O(N*logN)，也还是可以接受的，毕竟文件系统，如果是硬盘之类的，读写会很耗时间的。楼主斟酌。

#45

位图，如果内存放不下那么多bit，可以多次用位图