腾讯面试题:给40亿个不重复的unsigned int的数,没排序,然后再给一个数,如何快速间断这个数是否在那40亿个数中


腾讯面试题:给40亿个不重复的unsigned int的数,没排序,然后再给一个数,如何快速间断这个数是否在那40亿个数中?

这个题有点像《编程珠玑》里第二章A问题,但感觉不太一样,这题难道有低于O(n)的算法?
已邀请:

直接上位图了

开512M的空间, 刚好2^32个bit, 每个bit对应一个数, 一开始全为0
然后读这40亿个数, 读一个就把对应的bit置为1

然后直接查对应的bit是0还是1, 就好了

要回复问题请先登录注册

返回顶部