江苏龙网

  1. 主页 > 生活百科 > >

腾讯算法：判断一个数是否在40亿个整数中？最后附java代码

算法

题目最近看到一个题目：给40亿个不重复的 unsigned int 的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
解法搜了一下资料，该题目是腾讯的一道面试题，目前网上普遍给出的答案有两种 。
1.《编程珠玑》给出的方案我们把40亿个数中的每一个用32位的二进制来表示，假设这40亿个数开始放在一个文件中 。
然后将这40亿个数分成两类：

1.最高位为0 。
2.最高位为1 。
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了） 。
与要查找的数的最高位比较并接着进入相应的文件再查找 。
再然后把这个文件为又分成两类：1.次最高位为0；2.次最高位为1 。
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了） 。与要查找的数的次最高位比较并接着进入相应的文件再查找 。
.......
以此类推，就可以找到了,而且时间复杂度为O(logn) 。
此方案不是本文要讲的重点，只是把思路放在这边供大家参考 。
2.位图法思路
我们之所以无法将40亿个数字直接读取到内存去进行处理，是因为40亿个 unsigned int 的整数大约要占15G内存，正常情况下，没有这么大的内存，也不可能这样做 。
这种情况是因为一个整数占用了4个字节（Byte），而在本题中，我们其实只关心某个数字是否存在，在这种情况下，我们可以通过位图法来解决该问题 。
位图法思想：对于40亿个 unsigned int 的整数，每个数字用1个二进制数（一个二进制数占用1Bit，1Byte = 8Bit）来表示该数字是否存在，0为不存在，1为存在 。从低位开始数：
第1个二进制数表示整数0是否存在
 
第2个二进制数表示整数1是否存在
 
第3个二进制数表示整数2是否存在
 
依次类推 ... ...
第4294967296个二进制数用于表示整数4294967295是否存在 。
unsigned int 在32&64位编译器的范围为 0～4294967295，4294967296个二进制数大约占用512M内存，是一个可以接受的范围 。
例子题目：我们读取了3个整数：1、2、4，要判断整数3是否被读取过了 。
解答过程：
1）对于40亿个 unsigned int 的整数，我们可以定义4294967296个二进制数，并且全部初始化值为0 。
2）读取整数1：将第2个二进制数赋值为1，表示整数1是存在的，此时值为：10（高位还有4294967294个0，为了方便阅读不写出来，下文同） 。
3）读取整数2：将第3个二进制数赋值为1，表示整数2是存在的，此时值为：110 。
4）读取整数4：将第5个二进制数赋值为1，表示整数4是存在的，此时值为：1 0110 。
5）判断整数3是否被读取过，因为第1个二进制数表示整数0是否存在，因此整数3则通过第4个二进制数表示，此时的值为：1 0110，第4个二进制数为0，所以得出结论：整数3没有被读取过 。
JAVA实现由于Java中无法直接操作二进制数，因此我们可以通过 int 来实现 。1个二进制数占用1 Bit；1个 int 占用4 Byte，也就是32 Bit 。因此，我们可以使用1个int来表示32个二进制数 。
 
所以，我们有以下思路：
 
第1个int表示：整数0 ~ 31是否存在
 
第2个int表示：整数32 ~ 63是否存在
 
第3个int表示：整数64 ~ 95是否存在，依此类推 。
因此，我们最终可以使用一个int数组来表示4294967296个二进制数，通过数组的下标来指示第几个int 。
代码如下
package com.joonwhee.open.leetcode.temp;
/**
* 位图法
*
* @author joonwhee
* @date 2019/1/22
*/
public class BitMap {
/**
* 位图提供的最大长度,
* 比如unsigned int的最大值为4294967295,
* 则需要的length为4294967296
*/
private long length;
/**
* 位图桶
*/
private static int[] bitmapBucket;
/**
* int用来表示32位二进制数,
* BIT_VALUE[0]表示第1个二进制数存在、
* BIT_VALUE[1]表示第2个二进制数存在，以此类推
* <p>
* BIT_VALUE[0] = 00000000 00000000 00000000 00000001
* BIT_VALUE[1] = 00000000 00000000 00000000 00000010
* BIT_VALUE[2] = 00000000 00000000 00000000 00000100
* ...
* BIT_VALUE[31] = 10000000 00000000 00000000 00000000
*/
private static final int[] BIT_VALUE = https://www.isolves.com/it/cxkf/sf/2020-08-10/{


推荐阅读


上一篇：竹节虫是保护动物吗 竹节虫能活多久

下一篇：碟仙恐怖吗 玩碟仙会有什么后果