本文主要是介绍40亿个非负整数中找到出现两次的数和所有数的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
40亿个非负整数中找到出现两次的数和所有数的中位数
【题目】
32位无符号整数的范围是0-4294967295，现在有40亿个无符号整数，可以使用的最大内存是1GB，找出所有出现了两次的数。
【解答】
对于在很多整数中找出现次数的题，一般是使用哈希表对出现的每一个数做词频统计的。但是这个题只需要找出现2次的整数，如果还使用哈希表 key表示出现的数，value表示出现的数的次数，那么这样需要的内存空间更大，而且对于出现次数大于2次的数没必要再去统计，所以哈希表在此处有点不太合适。那么应该怎么计算呢，我们先计算一下，如果每一个数用2位来做词频统计，那么就包括了0次是00,1次是01，2次是10,3次是11，这样就足够了，也省下不少空间，一个数2位，40亿个数就是80亿位，也就是10亿字节，那么就需要大概1GB的空间来处理，刚好满足条件。
具体计算步骤如下：
1、申请开辟一个长度为4294967295*2的bit数组，即bitArray[4294967295*2]，占用内存空间约为1GB。
2、用bitArray数组的每2个位置表示一个出现的词频，遍历40亿个数，记为num，如果第一次出现num，则把
bitArray[num*2]和bitArray[num*2+1]置为01，num第二次出现就把bitArray[num*2]和bitArray[num*2+1]设
置为10，第三次出现就设置为11，如果大于3次出现则忽略不管，仍然保持11状态。
3、遍历bitArray数组，如果发现bitArray[i*2]和bitArray[i*2+1]的值是10，那么i就是出现了两次的数。
【进阶】
如果将内存改为10MB，怎么找到40亿个整数的中位数？
【解答】
这篇关于40亿个非负整数中找到出现两次的数和所有数的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
