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

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

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

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

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

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

思路分析：使用位存儲

如何存儲這32000個整數(shù)？

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

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

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

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

每個整數(shù)對應在位圖中的存儲狀態(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 對應的位圖值，和二進制值為：byteMap[0]	00000010
2 對應的位圖值，和二進制值為：byteMap[0]	00000100
3 對應的位圖值，和二進制值為：byteMap[0]	00001000
4 對應的位圖值，和二進制值為：byteMap[0]	00010000
5 對應的位圖值，和二進制值為：byteMap[0]	00100000
6 對應的位圖值，和二進制值為：byteMap[0]	01000000
7 對應的位圖值，和二進制值為：byteMap[0]	10000000
8 對應的位圖值，和二進制值為：byteMap[1]	00000001
9 對應的位圖值，和二進制值為：byteMap[1]	00000010
...

如何判斷是重復的？

既然我們用一個位(bit)代表一個數(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ū)傩裕ǔＳ枚M制位來表示，每個位代表一種狀態(tài)或?qū)傩?。在計算機科學中，位圖被廣泛用于各種應用，如圖像處理、數(shù)據(jù)壓縮、數(shù)據(jù)庫索引等。

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

復雜度：時間復雜度 O ( n ) O(n) O(n)、空間復雜度 O ( 1 ) O(1) O(1)

Go代碼

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

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

或者文章來源地址http://www.zghlxwxcb.cn/news/detail-676828.html

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 / 32
		offset := num0 % 32
		mark := 1 << offset
		if bitmap[index]&mark != 0 {
			duplicate = append(duplicate, num)
		} else {
			bitmap[index] |= mark
		}
	}
	return
}

到了這里，關(guān)于[Go版]算法通關(guān)村第十五關(guān)青銅——用4KB內(nèi)存尋找重復元素的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！