现在的位置: 首页 > 综合 > 正文

判断数字是否出现在40亿个数中?

2013年10月17日 ⁄ 综合 ⁄ 共 282字 ⁄ 字号 评论关闭

给40亿个不重复的unsigned int的整数,没排过序的,然后再给几个数,如何快速判断这几个数是否在那40亿个数当中?

 

思路:

unsigned int 的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存,用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0,然后每处理一个数字就将其对应的bit设置为1。当需要查询时,直接找到对应bit,看其值是0还是1即可。

 

原文链接:http://hi.baidu.com/mianshiti/blog/item/324a9003819da48ce950cd95.html

 

抱歉!评论已关闭.