电子商城网站开发流程,给个网站做导航违法吗,七里港网站建设,网站建设施工图片1.用4KB内存寻找重复元素
题目#xff1a;给定一个数组#xff0c;包含从1到N的整数#xff0c;N最大为32000#xff0c;数组可能还有重复值#xff0c;且N的取值不定#xff0c;若只有4KB的内存可用#xff0c;该如何打印数组中所有重复元素。 分析#xff1a; 本身是…1.用4KB内存寻找重复元素
题目给定一个数组包含从1到N的整数N最大为32000数组可能还有重复值且N的取值不定若只有4KB的内存可用该如何打印数组中所有重复元素。 分析 本身是一道海量数据问题的热身题如果去掉“只有4KB”的要求我们可以先创建一个大小为N的数组然后将这些数据放进来但是这里数组最大为32KB而题目有4KB的内存限制我们就必须先确定该如何存放这个数组。 如果只有4KB的空间那么只能寻址8*4*2^10个比特这个值比32000要大的因此我们可以创建32000比特的位向量(比特数组)其中一个比特位置就代表一个整数。 利用这个位向量就可以遍历访问整个数组。如果发现数组元素是v那么就将位置为v的设置为1碰到重复元素就输出一下。 创建一个长度为32000的数组每个位置存储0或者1因为要存的最大值可能是32000所以我们可以要存多大的数就在对应的位置0换成1即可比如存1数组第1位就是1索引是0其余位置是0。存100数组第100位就是1索引是99其余位置是0。存10000数组第9999位是1其余位置是0。如果在存某个数的时候发现这个位置是1那么这值就重复将这个值输出。 int是32位占空间4B,1B8bit,所以4kb空间就有超过4000*8个bit所以数组长度是320005,每个位置可以代表32个bit位 代码示例 public void checkDuplicates(int[] array) {BitSet bs new BitSet(320000);for (int i 0; i array.length; i) {int num array[i];int num0 num - 1;if (bs.get(num0)) {System.out.println(num);} else {bs.set(num0);}}}class BitSet {int[] bitset;public BitSet(int size) {this.bitset new int[size 5];}boolean get(int pos) {int wordNumber (pos 5);//除以32int bitNumber (pos 0x1F);//取余32return (bitset[wordNumber] (1 bitNumber)) ! 0;}void set(int pos) {int wordNumber (pos 5);//除以32int bitNumber (pos 0x1F);//取余32bitset[wordNumber] | 1 bitNumber;}}
