在之前的腾讯面试题中有这样的一道题:
给40亿个不重复的无符号整数,并且未排过序。如何判断一个数是否在这40亿个数中
这道题需要明白,40亿个无符号整数大约占16个G,而我们大多数电脑内存就是8个g,小部分的是16g,因此我们不能在内存中进行排序然后二分查找,而我们可以使用归并查找,那么时间复杂度大概是O(N*logN),空间复杂度还是O(N)
而如果我们要直接遍历查找,显然时间复杂度是O(N)
此时就要用到我们这篇博客所讲的——位图
位图的中心思想类似于哈希表,位图是使用二进制的比特位来表示一个数字在还是不在,在的话是1,不在的话是0。一个字节有八个比特位,因此一个字节就可以表示八个整数是否在还是不在。所以40亿个无符号整数只需要512mb左右就可以表示了
在java.util包中有官方的位图实现
import java.util.BitSet;
public class BitSetDemo {
public static void main(String[] args) {
int[] arr = {1,2,3,10,4,18,13};
BitSet bitSet = new BitSet(18);
for (int i = 0; i < arr.length; i++) {
bitSet.set(arr[i]);
}
System.out.println(bitSet.get(10));
}
}
我们只需要new一个BitSet对象,可以指定初始长度,不指定也可以,数据满了会自动扩容,然后用set方法传入一些值,用get方法就可以判断这些值在不在位图中了。
我们也可以自己实现一个BitSet
使用字节数组来存储数据,用usedSize来记录存储了多少数据
默认初始话的字节数组为1字节,如果要指定使用多少位,那么应该用这个数除以8(因为一字节对应八个比特位),而除后这个数可能有余数,因此要再加一
private byte[] elem;
private int usedSize;
public MyBitSet(){
this.elem = new byte[1];
}
/**
* 初始化set
* @param n 代表要使用多少位
*/
public MyBitSet(int n){
this.elem = new byte[n / 8 + 1];
}
先判断给定的val是否为负数,如果是负数,就抛出异常。
然后让给定的val除以8,得到的商就是在数组中的下标,而余数则是在数组中这个下标的对应左移的比特位
使用|=(1 << bitIndex),可以保证如果之前插入过这个值,不会影响这个值还是1,也不会更改别的值
最后,让usedSize++
如果arrayIndex大于数组长度减一,那么说明数组不够用,那么需要扩容
/**
* 将val转换为数组中的某一位,设置为1
* @param val
*/
public void set(int val) {
if(val < 0){
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8;
int bitIndex = val % 8;
//扩容
if(arrayIndex > elem.length - 1){
elem = Arrays.copyOf(elem,arrayIndex + 1);
}
elem[arrayIndex] |= (1 << bitIndex);
usedSize++;
}
同样的,先判断val是不是为负数,是负数就抛出异常
然后通过除8的余数和商得到在字节数组中的下标和左移的次数
然后用字节数组的这个下标对应的字节 & (1 << bitIndex),如果是1,说明这一位是1,那么说明这个数是存在的,返回true,否则返回0
public boolean get(int val) {
if(val < 0){
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8;
int bitIndex = val % 8;
if((elem[arrayIndex] & (1 << bitIndex)) != 0){
return true;
}
return false;
}
同样的,先判断val是不是为负数,是负数就抛出异常
然后通过除8的余数和商得到在字节数组中的下标和左移的次数
然后用字节数组的这个下标对应的字节 &= ~(1 << bitIndex),这样的话别的位上的值不会改变,而不管之前目标位是0还是1,都会被置为0
/**
* 将val的对应位置置为0
* @param val
*/
public void reset(int val){
if(val < 0){
throw new IndexOutOfBoundsException();
}
int arrayIndex = val / 8;
int bitIndex = val % 8;
elem[arrayIndex] &= ~(1 << bitIndex);
usedSize--;
}
/**
* 当前位图记录的元素个数
* @return
*/
public int getUsedSize(){
return usedSize;
}
public class Test {
public static void main(String[] args) {
int[] arr = {1,2,3,10,4,18,13};
MyBitSet myBitSet = new MyBitSet(18);
for (int i = 0; i < arr.length; i++) {
myBitSet.set(arr[i]);
}
System.out.println(myBitSet.get(10));
System.out.println(myBitSet.getUsedSize());
myBitSet.reset(10);
System.out.println(myBitSet.get(10));
}
}
通过从前往后获取字节数组的每一个字节,然后从后往前寻找每一个为1的位,可以从小到大的输出数组中存储的数据
需要注意的是,这里的elem[i] & (1 << j)应该判断是否不为0,而不是是否等于1,因为这里是按位于而不是&&
public void sort(){
for (int i = 0; i < elem.length; i++) {
for (int j = 0; j < 8; j++) {
if ((elem[i] & (1 << j)) != 0){
System.out.print(i * 8 + j + " ");
}
}
}
}
因篇幅问题不能全部显示,请点此查看更多更全内容
怀疑对方AI换脸可以让对方摁鼻子 真人摁下去鼻子会变形
女子野生动物园下车狼悄悄靠近 后车司机按喇叭提醒
睡前玩8分钟手机身体兴奋1小时 还可能让你“变丑”
惊蛰为啥吃梨?倒春寒来不来就看惊蛰
男子高速犯困开智能驾驶出事故 60万刚买的奔驰严重损毁