Java-怎样确定整数所在范围

Question

[宜搜笔试题]有一个确定的整数和40亿个杂乱无章的数字，怎样高效地确定这个整数是否在这40亿个整数之内？

Answer 1

这道算法题在编程珠玑上有一道比较相近的题。
若对内存没有限制，则可以使用位图/位向量来解决这个问题。
因为是java中的整数，所以是32位的整数，取值范围为：-2147483648~2147483647，用一个有2的32次方个位的位向量，第n位的0/1表示 这个取值范围的第n个整数是/否存在于这40亿个整数集合中，只需一遍预处理，后面的判断便会很快。
但是光是这个2的32次方个位的位向量，也已经占用了512MB的内存，所以有内存限制的时候，就需要考虑分治之类的策略了

Answer 2

需要先对40亿个整数进行预处理，对每个数字进行哈希处理，例如 整除1000求余数，将40亿个整数分散到小文件里。然后对确定的整数也进行哈希处理，找到对应的小文件，再遍历这个小文件比较该整数是否存在这个小文件里。

Answer 3

排序再查找，考察了这两类算法

Answer 4

如果要找的数是一个比较小的数字，一个一个的找也就是O(n)的时间。当然如果要找的数是n位的或许一位一位的比较用分治会快一些，也就是楼上的O(Nlog N)

Answer 5

这是个分而治之的问题，只是提一下思路请供借鉴。首先这么的数据肯定你不能放在一台机器一个内存中的，所以采取MapReduce的思路：先将这些数据分割成多份，每份分别有一台机器或者一个任务去处理这个数据是否在这个块中。

Answer 6

编程珠玑上看过，使用二分法更合理一点

Answer 7

见布隆过滤器

Answer 8

可以采用二分查找，先将这些数中最高位为1的放入一个文件，最高位为0的放入另外一个文件，然后判断要查找的数的最高位是0还是1，然后进一步查找。然后针对第二高位做重复的操作。这样就实现了折半。这样可能总的时间复杂度是O(nLogn)，但是如果要查找很多个整数的话，时间复杂度还是比较低的，之后再次查找只需O(logn)的时间。