用4KB內(nèi)存尋找重復(fù)元素
給定一個(gè)數(shù)組，包含從1到N的整數(shù)，N最大為32000，數(shù)組可能還有重復(fù)值，且N的取值不定，若只有4KB的內(nèi)存可用，該如何打印數(shù)組中所有重復(fù)元素。
如果不要求使用4KB，最簡單就是使用N長的數(shù)組然后將元素都存入數(shù)組，再打印，但是題目規(guī)定了4KB，很顯然這種做法就不大行了，一定會超出時(shí)間限制。文章來源：http://www.zghlxwxcb.cn/news/detail-683757.html
4KB=4 * 8 * 2 ^ 10 比特，這個(gè)值是大于32000，可以使用比特?cái)?shù)組來存儲相應(yīng)的元素。利用這個(gè)位向量，就可以遍歷訪問整個(gè)數(shù)組。如果發(fā)現(xiàn)數(shù)組元素是v，那么就將位置為v的設(shè)置為1，碰到重復(fù)元素，就輸出。代碼就沒什么可說的，真要實(shí)現(xiàn)起來，還是有一點(diǎn)復(fù)雜的。文章來源地址http://www.zghlxwxcb.cn/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;
}
}
}
到了這里，關(guān)于算法通關(guān)村——位運(yùn)算在查找重復(fù)元素中的妙用的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
