您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

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

时间:2020-08-10 10:26:54  来源:  作者:

题目

最近看到一个题目:给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 = {
0x00000001, 0x00000002, 0x00000004, 0x00000008,
0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800,
0x00001000, 0x00002000, 0x00004000, 0x00008000,
0x00010000, 0x00020000, 0x00040000, 0x00080000,
0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000,
0x10000000, 0x20000000, 0x40000000, 0x80000000};
/**
* length为1 - 32: 需要1个桶
* length为33 - 64: 需要2个桶
* ...
* 以此类推
*
* @param length
*/
public BitMap(long length) {
this.length = length;
// 根据长度算出,所需位图桶个数
bitmapBucket = new int[(int) (length >> 5) +
((length & 31) > 0 ? 1 : 0)];
}
/**
* 查找number是否存在于位图桶中
*
* @param number 要查询的数字
* @return true: number在位图桶中, 否则false
*/
public boolean getBit(long number) {
if (number < 0 || number > length) {
throw new IllegalArgumentException("非法参数");
}
// 计算该number在哪个桶
int belowIndex = (int) (number >> 5);
// 求出该number在桶里的下标(下标0 - 31)
int offset = (int) (number & 31);
// 拿到该桶的值
int currentValue = bitmapBucket[belowIndex];
// 计算该number是否存在
return ((currentValue & BIT_VALUE[offset])) == 0 ? false : true;
}
/**
* 将number在位图桶中标记为存在
*
* @param number 要标记的数字
*/
public void setBit(long number) {
// 合法性校验
if (number < 0 || number >= length) {
throw new IllegalArgumentException("非法参数");
}
// 计算该number在哪个桶
int belowIndex = (int) (number >> 5);
// 求出该number在桶里的下标(下标0 - 31)
int offset = (int) (number & 31);
// 拿到该桶的当前值
int currentValue = bitmapBucket[belowIndex];
// 将number在桶里标记
bitmapBucket[belowIndex] =
currentValue | BIT_VALUE[offset];
}
public static void main(String[] args) {
BitMap bitMap = new BitMap(4294967296L);
bitMap.setBit(4294967295L);
System.out.println(bitMap.getBit(4294967295L));
System.out.println(bitMap.getBit(4294967294L));
}
}

了解了思路后,代码就比较简单了。

1)通过构造函数传的 length 值,构建一个足够大的 int数组 bitmapBucket,对于题目的unsigned int 的整数,length为4294967296刚好够用。

 

2)将40亿个给定的数通过 setBit 方法,将对应的位置的二进制数标记为1(1代表存在)。

 

3)通过 getBit 方法判断给定的 number 是否存在于之前的40亿个数中。

setBit 例子:例如我们要将整数 32 标记为存在。

1)首先计算出整数 32 所在的位图桶下标为1,也就是bitmapBucket[1]。

 

2)接着计算出整数 32 在bitmapBucket[1] 桶中的下标0(下标0代表该桶的第1个二进制数)。

 

3)拿到bitmapBucket[1]当前值currentValue。

 

4)最后我们要将 bitmapBucket[1] 桶中第1个二进制数标记为1,并且不影响之前已经标记的二进制数,因此将 currentValue 与0000 0000 0000 0000 0000 0000 0000 0001 进行 ‘或’ 运算即可。而对于每一个二进制数,我们通过 BIT_VALUE来表示,这边的 0000 0000 0000 0000 0000 0000 0000 0001 ,可以通过 BIT_VALUE[0] 来表示。



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Tags: 算法  点击:(1)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  Tags: 算法  点击:(7)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 算法  点击:(16)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  Tags: 算法  点击:(24)  评论:(0)  加入收藏
基于算法的业务或者说AI的应用在这几年发展得很快。但是,在实际应用的场景中,我们经常会遇到一些非常奇怪的偏差现象。例如,Facebook将黑人标记为灵长类动物、城市图像识别系统...【详细内容】
2021-11-08  Tags: 算法  点击:(32)  评论:(0)  加入收藏
随着注册制的加速推进,新股越来越多,截止到今天A股上市公司的总数高达4500余家,A股一直就是重融资,轻投资的市场,而上市公司发行可转债这种再融资的(圈钱方式)是最能让普通投资者接...【详细内容】
2021-11-05  Tags: 算法  点击:(97)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 算法  点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  Tags: 算法  点击:(36)  评论:(0)  加入收藏
每个人都有过这样的经历:打开手机准备回消息或打电话,一看到微信图标右上方的小红点,于是忍不住先打开微信;看完微信,不知不觉又被另一个App牵引,直到关闭手机屏幕才发现自己早已...【详细内容】
2021-11-03  Tags: 算法  点击:(30)  评论:(0)  加入收藏
文丨互联网怪盗团在互联网行业,尤其是在投资人心目中,往往存在一种“算法迷信”或曰“技术迷信”:某公司的广告变现做得好,一定是因为有算法;某公司的云计算业务开展的好,也是因为...【详细内容】
2021-11-03  Tags: 算法  点击:(25)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条