试题
考点

算法-大数据相关算法-大数据相关算法

面5笔5

从2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数

前往“校招VIP”小程序,刷题更快
最新校招难题刷题,快来进刷题群吧
解答

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

评论

山山而川明明如月

2021-10-06 22:00:00

0 0

禾下乘凉

2021-06-27 08:54:35

0 0

加载更多