做百度网站排名软件,做购物网站的图标从哪里来,网站添加 百度商桥,知识付费做的最好的平台用4KB内存寻找重复元素
问题描述
给定一个数组#xff0c;包含从1到N的整数#xff0c;N最大为32000#xff0c;数组可能还有重复值#xff0c;且N的取值不定#xff0c;若只有4KB内存可用#xff0c;如何打印数组中所有的重复元素。
问题分析
Java中存储整数使用int…用4KB内存寻找重复元素
问题描述
给定一个数组包含从1到N的整数N最大为32000数组可能还有重复值且N的取值不定若只有4KB内存可用如何打印数组中所有的重复元素。
问题分析
Java中存储整数使用int或者long这里使用int就可以了。每一个int整数占四个字节320004B128KB题目中要求我们只使用4KB很明显我们不能使用int来存储最为节省空间的存储方式就是使用位来存储即bit4KB可以寻址48*2^103276832000,即对于从1到N的整数我们可以遍历数组,如果某个整数第一次出现将其对应的下标置1如果该整数再次被遍历到且下标为1则判定为重复。
代码实现
public void checkDuplicatesIn32000(int[] array) {BitSet bitSet new BitSet(32000);for (int i 0; i array.length; i) {int num array[i];int num0 num - 1;if(bitSet.get(num0)){System.out.println(num);}else {bitSet.set(num0);}}}
