在海量數(shù)據(jù)中，此時(shí)普通的數(shù)組、鏈表、Hash、樹等等結(jié)構(gòu)有無效了 ，因?yàn)閮?nèi)存空間放不下了。而常規(guī)的遞歸、排序，回溯、貪心和動(dòng)態(tài)規(guī)劃等思想也無效了，因?yàn)閳?zhí)行都會(huì)超時(shí)，必須另外想辦法。這類問題該如何下手呢？這里介紹三種非常典型的思路：

1. 使用位存儲(chǔ)，使用位存儲(chǔ)最大的好處是占用的空間是簡單存整數(shù)的1/8。例如一個(gè)40億的整數(shù)數(shù)組，如果用整數(shù)存儲(chǔ)需要16GB左右的空間，而如果使用位存儲(chǔ)，就可以用2GB的空間，這樣很多問題就能夠解決了。

2. 如果文件實(shí)在太大 ，無法在內(nèi)存中放下，則需要考慮將大文件分成若干小塊，先處理每個(gè)塊，最后再逐步得到想要的結(jié)果，這種方式也叫做外部排序。這樣需要遍歷全部序列至少兩次，是典型的用時(shí)間換空間的方法。

3. 堆，如果在超大數(shù)據(jù)中找第K大、第K小，K個(gè)最大、K個(gè)最小，則特別適合使用堆來做。而且將超大數(shù)據(jù)換成流數(shù)據(jù)也可以，而且?guī)缀跏俏ㄒ坏姆绞?#xff0c;口訣就是“查小用大堆，查大用小堆”。
   常識(shí)補(bǔ)充：10億 ≈ 1G、100萬 ≈ 1M

題目：用4KB內(nèi)存尋找重復(fù)元素

給定一個(gè)數(shù)組，包含從1到N的整數(shù)，N最大為32000，數(shù)組可能還有重復(fù)值，且N的取值不定，若只有4KB的內(nèi)存可用，該如何打印數(shù)組中所有重復(fù)元素。

思路分析：使用位存儲(chǔ)

如何存儲(chǔ)這32000個(gè)整數(shù)？

常規(guī)思路分析：32000個(gè)整數(shù)，整數(shù)用int表示，一個(gè)int占用4個(gè)字節(jié)(byte)，32000個(gè)整數(shù)所需內(nèi)存就是 ：

32000 * 4 = 128000（byte）
32000 * 4 / 1024 = 125（KB）
125（KB） > 4（KB）	//可見，已經(jīng)超過題目要求的4KB內(nèi)存要求。

下面我們使用位存儲(chǔ)的方式：1個(gè)字節(jié)(byte)=8位(bit)，32000個(gè)正數(shù)用32000個(gè)位就是：

32000 / 8 = 4000（byte）
32000 / 8 / 1024 = 3.9（KB）
3.9（KB）< 4（KB）	//如此，就滿足題意，使用了4KB就能存儲(chǔ)32000個(gè)元素

每個(gè)整數(shù)對(duì)應(yīng)在位圖中的存儲(chǔ)狀態(tài)舉例

原數(shù)據(jù)：				1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18  ...
該值在位圖中的索引值：	0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  2  2  2  ... 
該值在位圖中的偏移量：	1  2  3  4  5  6  7  0  1  2  3  4  5  6  7  0  1  2  ...1 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[0]	00000010
2 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[0]	00000100
3 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[0]	00001000
4 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[0]	00010000
5 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[0]	00100000
6 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[0]	01000000
7 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[0]	10000000
8 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[1]	00000001
9 對(duì)應(yīng)的位圖值，和二進(jìn)制值為：byteMap[1]	00000010
...

如何判斷是重復(fù)的？

既然我們用一個(gè)位(bit)代表一個(gè)數(shù)值，那么該位的兩種狀態(tài)0或1，就可以用于判斷該值是否存在。
例如：字節(jié)00001101表示以下情況：

• 第 0 位（最低位）為 1，表示數(shù)字 1 出現(xiàn)過。
• 第 1 位為 0，表示數(shù)字 2 沒有出現(xiàn)過。
• 第 2 位為 1，表示數(shù)字 3 出現(xiàn)過。
• 第 3 位為 1，表示數(shù)字 4 出現(xiàn)過。
• 后續(xù)位為 0，表示數(shù)字 5 到 8 都沒有出現(xiàn)過。

mark := 1 << offset	//offset 就是偏移量
if (bitmap[index] & mask) != 0 {// 位已經(jīng)被設(shè)置，說明數(shù)字出現(xiàn)過
}
bitmap[index] |= mask	//設(shè)置該位值為1

具體的步驟

位圖（Bitmap）是一種數(shù)據(jù)結(jié)構(gòu)，用于表示一組元素的狀態(tài)或?qū)傩?#xff0c;通常用二進(jìn)制位來表示，每個(gè)位代表一種狀態(tài)或?qū)傩?。在?jì)算機(jī)科學(xué)中，位圖被廣泛用于各種應(yīng)用，如圖像處理、數(shù)據(jù)壓縮、數(shù)據(jù)庫索引等。

1. 初始化位圖：由于N最大是32000，可以是哦用一個(gè)長度為32000/8=4000的位圖，每個(gè)位可以表示一個(gè)整數(shù)。
2. 遍歷數(shù)組，對(duì)于數(shù)組中的每個(gè)元素：
   • 計(jì)算x在位圖中的索引和位偏移。例如：x=5，則索引為5/8=0，位偏移為5%8=5。
   • 檢查位圖的索引位置是否已經(jīng)被標(biāo)記。
     • 如果未被標(biāo)記，則將其標(biāo)記為已訪問；
     • 如果已經(jīng)被標(biāo)記，則說明x是重復(fù)的，打印x。
3. 打印重復(fù)元素。

復(fù)雜度：時(shí)間復(fù)雜度$O(n)$、空間復(fù)雜度$O(1)$

Go代碼

源碼地址： GitHub-golang版本（含單元測試代碼）

func FindDuplicatesIn32000(arr []int) (duplicate []int) {N := 32000bitmap := make([]byte, N/8+1)for _, num := range arr {// 計(jì)算 num 在 bitmap 中的索引// index := num / 8index := num >> 3// 計(jì)算 num 在 bitmap 中的偏移量offset := num % 8mark := byte(1 << offset)if bitmap[index]&mark != 0 {duplicate = append(duplicate, num)} else {bitmap[index] |= mark}}return
}

或者

func FindDuplicatesIn32000(arr []int) (duplicate []int) {N := 32000// 或者這里不用+1，只要索引是base0的即可bitmap := make([]int, N/32)for _, num := range arr {num0 := num - 1 //base0開始index := num0 / 32offset := num0 % 32mark := 1 << offsetif bitmap[index]&mark != 0 {duplicate = append(duplicate, num)} else {bitmap[index] |= mark}}return
}