实现一个位图、100亿个整数找出只出现一次的整数。

        实现一个位图,100亿个整数找出只出现一次的整数、找出现次数不超过2次的数。这种类似的题,

        先理解位图,位图是在数据量非常大,无法使用Hash表时使用,用两个为表示一个整数,00表示未出现,01表示出现一次,10表示出现两次,11表示超过两次(整数对应位图位置比如第100个整数(如果从0开始整数就是99,如果从-2^32开始整数就是-2^32+99)在第100*2,和100*2加一,这两个位置)。

        一个字节(1B8位(8b)存4个整数,int型有2^32个整数,耗费总内存2^32 / 4 / 1024 / 1024 / 1024 = 1(GB)

另一类型题,给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集。

        先对一个文件整型存放进位图,再将另一个文件整数与位图进行对比即可。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-10 14:00
林子大了什么鸟都有啊,我觉得我说的已经很客气了,阴阳谁呢
牛客62656195...:应该不是阴阳吧?你第一次注册的时候boss就说你是牛人
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务