题目
32位无符号整数范围是0---4294967295,现在有40亿个无符号整数,可以最多使用1GB的内存,找出所有出现了2次的数
原题目的解决方法
4294967295的bit数组的大小是500MB,我们申请bit Arr是数组,长度是42949672952,大小恰好为1GB,这个时候如果第一遇到num,那么我们把bitArr[num2]和bitArr[num2+1]置为01,如果是第二次遇到bitArr[num2]和bitArr[num2+1]置为10,第三次遇到bitArr[num2]和bitArr[num2+1]置为11,
第四次以及以上就不改变了.这个时候bitArr就生成了,再出bit[i2]和bit[i*2+1]为10的数,对应的i就是出现了两次的数.
补充题目
可以使用最多10MB的内存,怎么要找到40亿个整数的中位数.
分析
使用10MB的内存.所以我们想到要通过分区间的方式处理,那我们分多少个区间哪,每一个区间长度为长度为2MB,那么占空间大小为8MB...具体看书
图片.png
.现在10MB的空间还没有被分配,我们接下来就是.创建一个数组arr[0...2147],然后遍历这40亿个数,然后遍历到的每个数,都让这些书对应的区间加加,遍历完之后,我们找第20个亿的数放在哪个位置(因为是中位数,然后这个又是按照顺序存储的)
图片.png
所以真正的用到10MB限制的是,已经确定了中位数的区间和在区间上的位置.
这个时候我们遍历40亿个数,其中只关心这个区间上的数,因为当前的区间可能有重复的值,所以要计算词频,最后恰好是第0.002亿的数就是结果(0.002亿是举的例子)
