算法-大数据相关算法-大数据相关算法
面5笔5从2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数
对整数,可以考虑用位图法,因为本题需要辨别不存在、出现一次和出现多次三个状态,一个二进位制0和1满足不了需求,
所以一个数用两个二进制位表示,00表示不存在,01表示出现一次,11出现多次
则2.5亿整数需要的内存数为232 * 2bit = 1GB, 普通电脑即可满足,即用232 * 2个二进制位来标识所有的整数,每两位依次记录整数1,2,3,4..
读取文件的整数,算出对应的二进制位数,如果是00,则改为01;是01,则改为11;
全部处理完后,取其中标记为11的位数,计算出其所代表的整数值就得到所求结果