wordpress门户站,led灯网站策划书,类似一起做网店的网站,小网站建设公司排名引言阿里内推面试的时候被考了一道编程题#xff1a;10亿个范围为1~2048的整数#xff0c;将其去重并计算数字数目。我看到这个题目就想起来了《编程珠玑》第一章讲的叫做BitMap的数据结构#xff0c;但是我并没有在java上实现过#xff0c;这就比较尴尬了#xff0c;再加…引言阿里内推面试的时候被考了一道编程题10亿个范围为1~2048的整数将其去重并计算数字数目。我看到这个题目就想起来了《编程珠玑》第一章讲的叫做BitMap的数据结构但是我并没有在java上实现过这就比较尴尬了再加上时间不多了只好暂时用byte代替bit浪费7个字节在这篇文章里总结一下BitMap的常用代码以免重蹈覆辙。偷懒的方法其实java.util包中已经有了一个实现可以用这个数据结构偷懒写了一个Demo如下package org.du.offerproblem.bitmap;import java.util.BitSet;/*** Created by 燃烧杯 on 2018/2/24.*/public class BitSetTest {public static void main(String[] args) {int [] array new int [] {1,2,3,22,0,3,63};BitSet bitSet new BitSet(1);System.out.println(bitSet.size()); //64bitSet new BitSet(65);System.out.println(bitSet.size()); //128bitSet new BitSet(23);System.out.println(bitSet.size()); //64//将数组内容组bitmapfor(int i0;i{bitSet.set(array[i], true);}System.out.println(bitSet.get(22));System.out.println(bitSet.get(60));System.out.println(下面开始遍历BitSet);for ( int i 0; i bitSet.size(); i ){System.out.println(bitSet.get(i));}}}java.util.BitSet的底层是long数组.size()方法返回的是BitSet当前位数因为long是64位的所以size返回的值也是64的整数倍所以在上面的代码中发现我在构造函数中传入初始化长度1~64中的任意一个值size的大小都是64位因为此时long数组的长度只有1而我一旦将其设置成65size的大小就变成128了。用这个类是个偷懒的好办法但是一旦面试官一定要让你自己实现一个就不行了。自己实现BitMap可以用int数组来实现一个BitMap这种方法最关键的是求出index在int数组中的位置以及在该位置上的偏移量有如下公式int数组中的位置(belowIndex) (index - 1) 5偏移量(offset) (index - 1) 31我们这里假设index是从1开始的所以先将index减去1如果你要统计的数据范围是从0开始的则不需要减去这个1。右移5位(相当于除以32)的原因是一个int型数据是32位的(2的5次方等于32)。偏移量中31相当于模32其原因也因为int型数据是32位的。如果你不准备基于int而是准备基于其他的如bytelong的话(以byte为例)则将5改成331改成7即可。setBit的流程如下求出belowIndex并且得到int值求出offset并且利用“或运算”将刚才得到的int值的offset位置置为1getBit的流程如下求出belowIndex并且得到int值求出offset之后利用“与运算”取出offset位置的值将其变为01后返回代码如下package org.du.offerproblem.bitmap;/*** 实现BitMap*注这个bitMap的index是从1开始的*/public class BitMap {private long length;private static int[] bitsMap;//构造函数中传入数据中的最大值public BitMap(long length) {this.length length;// 根据长度算出所需数组大小bitsMap new int[(int) (length 5) ((length 31) 0 ? 1 : 0)];}public int getBit(long index) {int intData bitsMap[(int) ((index - 1) 5)];int offset (int) ((index - 1) 31);return intData offset 0x01;}public void setBit(long index) {// 求出该index - 1所在bitMap的下标int belowIndex (int) ((index - 1) 5);// 求出该值的偏移量(求余)int offset (int) ((index - 1) 31);int inData bitsMap[belowIndex];bitsMap[belowIndex] inData | (0x01 offset);}public static void main(String[] args) {BitMap bitMap new BitMap(32);bitMap.setBit(32);System.out.println(bitMap.getBit(1));System.out.println(bitMap.getBit(32));}}使用BitMap进行数据去重下面给出数组去重的代码package org.du.offerproblem.bitmap;import java.util.Arrays;/*** Created by 燃烧杯 on 2018/2/24.* 这个BitMap的去重是从0开始*/public class BitMapRepRemove {//public static final int _1MB 1024 * 1024;//public static byte[] flags new byte[ 512 * _1MB ];public static byte[] flags;public static void main(String[] args) {int[] array {255, 1024, 1024, 0, 65536, 0, 1024, 8888, 9999, 1111, 8888};int length 65536 1;flags new byte[(int) (length 3) ((length 7) 0 ? 1 : 0)];int index 0;for(int num : array) {if( getFlags(num) ! 1) {//未出现的元素array[index] num;index index 1;//设置标志位setFlags(num);}}array Arrays.copyOf(array, index);System.out.println(Arrays.toString(array));System.out.println(array.length);}public static void setFlags(int num) {int offset num (0x07);flags[num 3] | 0x01 offset;}public static int getFlags(int num) {int offset num (0x07);return flags[num 3] offset 0x01;}}
