用4KB内存寻找重复元素
给定一个数组,包含从1到N的整数,N最大为32000,数组可能还有重复值,且N的取值不定,若只有4KB的内存可用,该如何打印数组中所有重复元素。
如果不要求使用4KB,最简单就是使用N长的数组然后将元素都存入数组,再打印,但是题目规定了4KB,很显然这种做法就不大行了,一定会超出时间限制。文章来源:https://www.toymoban.com/news/detail-683757.html
4KB=4 * 8 * 2 ^ 10 比特,这个值是大于32000,可以使用比特数组来存储相应的元素。利用这个位向量,就可以遍历访问整个数组。如果发现数组元素是v,那么就将位置为v的设置为1,碰到重复元素,就输出。代码就没什么可说的,真要实现起来,还是有一点复杂的。文章来源地址https://www.toymoban.com/news/detail-683757.html
public class FindDuplicatesIn32000 {
public void checkDuplicates(int[] array) {
BitSet bs = new BitSet(32000);
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);//除以32
int bitNumber = (pos & 0x1F);//除以32
return (bitset[wordNumber] & (1 << bitNumber)) != 0;
}
void set(int pos) {
int wordNumber = (pos >> 5);//除以32
int bitNumber = (pos & 0x1F);//除以32
bitset[wordNumber] |= 1 << bitNumber;
}
}
}
到了这里,关于算法通关村——位运算在查找重复元素中的妙用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!