校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 算法 > 大数据相关算法
题目

从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的位数,计算出其所代表的整数值就得到所求结果。

C 0条回复 评论

帖子还没人回复快来抢沙发