如何从2亿个随机整数中找出中间值?

看到这个问题时,相信大多数人都会想:“这不是很简单嘛,先排序,然后最中间那个数不就是了?”

好像很有道理,但是大家往往忽略了一个问题,2亿个32位的整数就要占用4GB的内存空间,而内存空间往往不像我们想象中的那么充裕。

“那么,使用归并排序呢?每次先排序小部分。”,归并排序有一个不可避免的问题,虽然排序一小部分的时候占用的内存较小,但是总归是要合并到一起的,最终完全合并的时候还是需要占用4GB的内存。

那么我们还能怎么办?别急,我们来慢慢分析一下。

2亿个随机整数还可以分为两种情况,一种是2亿个不重复的随机整数,另一种是2亿个有重复项的随机整数。由于题目并没有指出数据中是否有重复项,所以我们只能按照有重复项的情况来解决。

2亿个(有重复项的)随机整数

既然内存空间不够用,那我们能不能不把这些数据读入到内存中,而是直接在硬盘中直接排序?

但是!我们要知道,直接在硬盘中对数据进行排序的话需要多次读写硬盘,巨量的读写操作会消耗大量的性能,并且速度也比较慢。说直白点就是:可以,但是这种方法简直蠢死了。

那我们要怎么办啊?似乎是走投无路了。

别着急,你有没有发现题目虽然说让我们找出这些数的中间值,但是并没有要求我们对数据进行排序,只是我们自己绕进了排序的怪圈中。

我们只需要找出这些数据中,按大小排序处于第一亿位和第一亿零一位的两个数即可,而且我们可以利用一种很巧妙的方法来找到这两个数。

这是一种近似于二分查找思想的方法,我们可以在最开始的时候,以0为分界线,对所有整数进行遍历并统计小于0的整数个数和大于等于0的整数个数,假设小于0的整数有94,632,563个,那么大于等于0的数就有105,367,437个,这也就意味着,我们需要的那两个数是大于等于0的。

接下来我们就可以向第一次遍历那样对数据进行拆分了,我们知道int类型正整数最大值是2^31,那么第二次遍历我们就以2^30作为分界线吧,统计小于2^30的数与大于等于2^30的数,假设小于2^30的数有36,524,163个,大于2^30次方的数有68,843,274个,那么我们需要的那两个数处于02^30-1这个闭区间内。

按照这个方法,一次又一次第进行遍历,当我们统计出我们需要的那两个数处于某一个区间内,并且这个区间内的数比较少,至少能让我们直接在内存中进行排序时,我们就可以将符合这个区间的数全部读取到内存中排序,比如:

假设第一亿个数和第一亿零一个数是大于等于1,065,236且小于3,216,320的,并且我们统计到在这个区间内只有21,365个数,小于1,065,236的数有99,989,764个,这时候我们就可以将这21,365个数直接读入到一个数组中,对这个数组中的数据进行排序,第一亿个数即为排序完毕后的数组中的第10,236个数,而第一亿零一个数则为排序后的数组中的10,237个数。

怎么样?我们并没有对这2亿个整数进行排序,但依然找到了我们想要的这两个数字。

2亿个(不重复的)随机整数

如果题目中提到的随机整数不存在重复项那就好办了,我们可以利用一种效率极高的算法来进行排序——位图排序

位图排序是一种空间换时间的排序算法,时间复杂度仅为O(n),但它的限制很多,比如数据不能有重复项,在排序之前必须知道数据的范围(最小值及最大值,或者大致范围),范围越宽广,占用的内存空间就越大。

打个比方,假设有一万个不重复的整数,已知这些整数里最小的数为0,最大的数为100,000,这时候,我们可以申请一个长度为100,001位的内存空间(即97.66KB),然后遍历这一万个整数并且将内存空间中对应位置的位设为1,在遍历结束后排序也已经结束了。

可能这段话还不是很能让你理解透彻,这样吧,把数据量再缩小一些,比如有[19, 36, 3, 42, 11, 26, 5, 9, 24]这样一个数组,假设我们已经知道这个数组最小值为3,最大值为42,这时候我们就可以申请一个长度为40位的内存空间,如下:

00000 00000 00000 00000 00000 00000 00000 00000

(为了看起来方便,这里以5位相隔一个空格来表示)

对该数组进行遍历,并且将每个整数的值减去3之后,将对应位置设为1,结果如下:

10100 01010 00000 01000 01010 00000 00010 00001

从这串01中,我们能看到这里的第0位、第2位、第6位都为1,这几个1的位置加上数组中的最小值3则表示的是3, 5, 9这几个数。

说到这应该就能明白了吧,在排序完成后,只需要遍历一遍这个内存空间中的每一位就能输出排序后的数组。

在数据不重复的情况下,我们可以使用位图排序来对题目中的2亿个数据进行排序,随后遍历内存空间,遍历到第一亿个1的时候,这个1及下一个1所在的位置的平均值则为中间值。

什么?题目没有给出数据范围?其实是有的,int类型能表示的范围是-2^312^31之间,因此我们其实只需要2^32位的内存空间(即4GB)即可表示int类型所能表示的所有整数。

哈哈,开个玩笑,位图排序的使用限制实在是太多了,所以这道题,并不适合位图排序,这里只是心血来潮对位图排序做一个简单的介绍~

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注