面试题

给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这 40 亿个数中。

• 遍历，时间复杂度 O(N)

• 排序 O(NlogN)，利用二分查找：logN

• 位图解决：

  数据是否在给定的整型数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在，如果二进制比特位为 1，代表存在，为 0 代表不存在。

  

位图概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。