骨骼型的网站,可以免费注册网站,简单易做的的网站,wordpress word插件有这样的一个问题#xff1a;
给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这40亿个数 中。
那么我们一般会想到这样做的
1.遍历#xff0c;时间复杂度O(n)
2.排序#xff08;N*logN#xff09;#xff0c…有这样的一个问题
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数 中。
那么我们一般会想到这样做的
1.遍历时间复杂度O(n)
2.排序N*logN然后二分查找
那么此时此刻我们再次细想一下这些方法一般放在内存中进行的那么40亿个不重复的无符号整数有多大容量呢
首先10亿个字节大概是1个G
那么10亿个整数大约是4个G
然后呢40亿个整数大约是16个G
所以如若这么大容量放到电脑内存上跑恰好此时电脑内存也是16个G那么不是刚刚好
其实不然电脑上不单单只是跑这个程序后面还有很多比如微信啊爱奇艺什么的所以一般来说这么大容量放到16G的电脑内存是不太现实的。
那么还有什么解决办法呢
那就请出今天的主角之一位图
位图
那么什么又是位图呢 这里说的位图指的是数据结构当中的不是那个指图像那个位图哦
位图所谓的位图就是用每一位来存放某种状态的。
适用于海量数据整数数据无重复的场景。通常用来判定某个数据存不存在的。
那么举个例子来看看 我这里假设有了一个字节数组然后有三个字节那么一个字节呢又对应8个比特位
一个比特位呢又可以代表0/1两种状态。
所以数组arr中每个数字可以通过某个算式来确定某个位置然后将某个位置的比特位设置为1说明此数字存在。
比如就11来说
11/81
那么我们就放到这个1下标
11%83
那么我们就在数组1下标下的第三个比特位设置为1
然后可以说明数字是存在过的
这里值得注意下为什么比特位标明的数字从右到左呢
这里是为了方便自己也是可以左到右的。 那么回过头细想一下一个字节有8个比特位且8个比特位都可以表示状态。
那么10亿个字节大概是0.9G接近1G
10亿个比特位大概是119兆看作128兆
那么40亿个比特位那么就是可以看作512兆。
所以内存量一下子大大缩小了。
那么你看这个位图是不是很强大呢
ok那么接下来讲讲如何实现它吧。
由上述刚刚的例子可以看得出底层还是一个数组来的而且还是一个字节数组。
然后呢我们创建它的时候默认给定一个容量。
但是有时候需要用户指定它需要范围是多大那么可以这样写。 //位图底层还是一个数组public byte [] elem;//记录存放数据多少public int Usize;public MyBitMap(){//默认给定的数组大小是1个字节this.elemnew byte[1];}public MyBitMap(int n){this.elemnew byte[n/81];}
在给定参数的构造方法中假设我们给定数字范围是10个那么10/81但是还余下两个9 10
所以我们直接给多一个字节是可以的。set
那么接着讲讲set吧
set
思路 当然这是核心思路然后代码实现方面还是需要考虑一些细节
比如我们set方法参数传入一个数字的话如若数字给到的是0的数字那么此时是不符合我们位图的
再者如果是给定的数字如若在找数组下标时超出数组范围这时候也是需要处理的比如扩容操作。
那么代码如下 public void set(int val){if(val0){//需要抛出异常因为会导致数组越界throw new IndexOutOfBoundsException();}//放到字节数组哪个位置int arrIndexval/8;if(arrIndexelem.length){//超出数组范围进行扩容elem Arrays.copyOf(elem,arrIndex1);}//放到字节数组位置的哪个比特位int bitIndexval%8;elem[arrIndex] |(1bitIndex);Usize;}
这个找哪个比特位进行修改其实最开始时讲过了
即val/8字节数组哪个下标
val%8下标内哪个比特位。
所以这里我们就可以找到哪个字节哪个比特位要进行修改状态比如举的例子设置5这个数字
5/80即在数组0下标
5%85即在比特位第六个位置
get
这个get方法是返回这个数字是否是存在过的。
所以呢我们还得是找到这个数字在哪先然后判断下这个数字的比特位是否是1
举例 代码
public boolean get(int val){if(val0){throw new IndexOutOfBoundsException();}int arrIndexval/8;int bitIndexval%8;if((elem[arrIndex](1bitIndex))!0){return true;}return false;}
reset
reset方法呢是把传入参数对应的比特重新置为0
举例说明 代码 public void reset(int val){if(val0){throw new IndexOutOfBoundsException();}int arrIndexval/8;int bitIndexval%8;elem[arrIndex] ~(1bitIndex);Usize--;}public int getSize(){return Usize;}
值得注意的是进行set的时候Usize了
所以写一个方法方法来返回当前设置的个数。
那么位图一些基本方法写完了这里还差最后一个方法排序
排序
其实我们位图是可以排序的
拿这里来说 只要我们从右边开始遍历当前比特位是1的就可以输出当前的值
那么判断当前位是不是为1是get方法里的思路是一致的用上
那么如何输出当前的数字呢
比如我要输出的是5那么此时我们可以这样vali*8j
当前的i0因为我们输出的数字是5在字节数组的0下标当j从下标开始遍历j5时就可以输出这个数字5了
代码 public static void main(String[] args) {int [] arrnew int[]{3,10,9,5,7,24,18};MyBitMap myBitMapnew MyBitMap(24);//先把数据放进字节数组中for(int i0;iarr.length;i){myBitMap.set(arr[i]);}//排序for(int i0;i myBitMap.elem.length;i){for(int j0;j8;j){if((myBitMap.elem[i](1j))!0){System.out.print(i*8j );}}}}
ok那么位图这里小编分享的差不多了。
顺带提一句一开始给的那道题是腾讯曾经的面试题来的。 源码
public class MyBitMap {//位图底层还是一个数组public byte [] elem;//记录存放数据多少public int Usize;public MyBitMap(){//默认给定的数组大小是1个字节this.elemnew byte[1];}public MyBitMap(int n){this.elemnew byte[n/81];}/*** set操作对添加进来的数据置为1即为存在的意思* param val*/public void set(int val){if(val0){//需要抛出异常因为会导致数组越界throw new IndexOutOfBoundsException();}//放到字节数组哪个位置int arrIndexval/8;if(arrIndexelem.length){//超出数组范围进行扩容elem Arrays.copyOf(elem,arrIndex1);}//放到字节数组位置的哪个比特位int bitIndexval%8;elem[arrIndex] |(1bitIndex);Usize;}/*** get方法返回比特位是否设置过1* param val* return*/public boolean get(int val){if(val0){throw new IndexOutOfBoundsException();}int arrIndexval/8;int bitIndexval%8;if((elem[arrIndex](1bitIndex))!0){return true;}return false;}public void reset(int val){if(val0){throw new IndexOutOfBoundsException();}int arrIndexval/8;int bitIndexval%8;elem[arrIndex] ~(1bitIndex);Usize--;}public int getSize(){return Usize;}public static void main(String[] args) {int [] arrnew int[]{3,10,9,5,7,24,18};MyBitMap myBitMapnew MyBitMap(24);//先把数据放进字节数组中for(int i0;iarr.length;i){myBitMap.set(arr[i]);}//排序for(int i0;i myBitMap.elem.length;i){for(int j0;j8;j){if((myBitMap.elem[i](1j))!0){System.out.print(i*8j );}}}}
}
