題目要求：給定一個(gè)數(shù)組，包含從1到N的整數(shù)，N最大為32000，數(shù)組可能還有重復(fù)值，且N的取值不定，若只有4KB的內(nèi)存可用，該如何打印數(shù)組中所有重復(fù)元素。
思路：
直接用大小為32000的int數(shù)組來標(biāo)記對(duì)應(yīng)下標(biāo)下的值出現(xiàn)次數(shù)，但是空間大小是32000*4B超過了4KB
這里采用一種壓縮空間的方式——位圖，每一位表示對(duì)應(yīng)的一個(gè)整數(shù)，用32000位就能代表32000個(gè)整數(shù)，直接每個(gè)元素節(jié)省了一個(gè)int大小也就是4B的空間。
初始化數(shù)組時(shí)：this.bitset = new int[size >> 5]? =>?每32縮小一個(gè)int大小
set時(shí)：先獲取pos除以32的整數(shù)部分，再獲取pos除以32的余數(shù)
例如34，先34>>5等于1，再34&(11111)等于2（00010），對(duì)應(yīng)bitset[1]中的第2位
bitset[0]對(duì)應(yīng)1-32
bitset[1]對(duì)應(yīng)33-64文章來源：http://www.zghlxwxcb.cn/news/detail-703448.html
這樣就能每一個(gè)bitset用32位表示32個(gè)int文章來源地址http://www.zghlxwxcb.cn/news/detail-703448.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);
int bitNumber = (pos & 0x1F);
return (bitset[wordNumber] & (1 << bitNumber)) != 0;
}
void set(int pos) {
int wordNumber = (pos >> 5);
int bitNumber = (pos & 0x1F);
bitset[wordNumber] |= 1 << bitNumber;
}
}
}
到了這里，關(guān)于算法通關(guān)村第11關(guān)【黃金】| 用4KB內(nèi)存尋找重復(fù)元素的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[Go版]算法通關(guān)村第十二關(guān)黃金——字符串沖刺題](https://imgs.yssmx.com/Uploads/2024/02/657183-1.png)
![[Go版]算法通關(guān)村第十五關(guān)黃金——繼續(xù)研究超大規(guī)模數(shù)據(jù)場(chǎng)景的問題](https://imgs.yssmx.com/Uploads/2024/02/693875-1.png)
![[Go版]算法通關(guān)村第十三關(guān)黃金——數(shù)字?jǐn)?shù)學(xué)問題之?dāng)?shù)論問題（最大公約數(shù)、素?cái)?shù)、埃氏篩、丑數(shù)）](https://imgs.yssmx.com/Uploads/2024/02/668230-1.png)
