點陣圖法

例如，要判斷一千萬個人的狀態，每個人只有兩種狀態：男人，女人，可以用0，1表示。那麼就可以開一個int數組，一個int有32個位，就可以表示32個人。操作的時候可以使用位操作。

一、給40億個不重複的unsigned int的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中

申請512M的內存

一個bit位代表一個unsigned int值

讀入40億個數，設置相應的bit位

讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在

二、使用點陣圖法判斷整形數組是否存在重複

判斷集合中存在重複是常見編程任務之一，當集合中數據量比較大時我們通常希望少進行幾次掃描，這時雙重循環法就不可取了。

點陣圖法比較適合於這種情況，它的做法是按照集合中最大元素max創建一個長度為max+1的新數組，然後再次掃描原數組，遇到幾就給新數組的第幾位置上1，如遇到 5就給新數組的第六個元素置1，這樣下次再遇到5想置位時發現新數組的第六個元素已經是1了，這說明這次的數據肯定和以前的數據存在著重複。這種給新數組初始化時置零其後置一的做法類似於點陣圖的處理方法故稱點陣圖法。它的運算次數最壞的情況為2N。如果已知數組的最大值即能事先給新數組定長的話效率還能提高一倍。

示例代碼如下：

package com.sitinspring;

public class DuplicatedArrayTest {

public static void main(String[] args) {

int [][] arr = {

{ 1 , 2 , 3 , 5 , 3 , 5 , 56, 534 , 3 , 32 } ,

{ 1 , 2 , 3 , 5 } ,

{ 1 , 2 , 3 , 5 , 3 , 5 } ,

{ 0 , 0 , 1 , 2 , 3 , 5 , 56, 534 , 78 , 32 } ,

} ;

for ( int i = 0 ;i

System.out.print( " 數組: " );

for ( int temp:arr[i]) {

System.out.print(temp + ", " );

}

System.out.print( " 中 " );

System.out.print(hasDuplicatedItem(arr[i]) ? " 存在 " : " 不存在 " );

System.out.print( " 重複元素.\n ");

}

}

public static boolean hasDuplicatedItem( int [] arr) {

// 掃描數組找最大值

int max = arr[ 0 ];

for ( int i = 1 ;i

if (arr[i] > max) {

max = arr[i];

}

}

// 按最大值創建一個新數組

int [] bitArray = new int [max +1 ];

// 按值向新數組中添值，如value為3則bitArray[3]=1

for ( int value:arr) {

if (bitArray[value] != 0 ) {

// 如果value指向的位置已經不是零，說明之前已經給這一塊置1了，立即返回true表示數組有重複

return true ;

}

else {

// value指向的位置是零，則置為1表示這一位已經有數存在了

bitArray[value] = 1 ;

}

}

return false ;

}

}

輸出：

數組: 1 , 2 , 3 , 5 , 3 , 5 , 56 , 534 , 3 , 32 ,中存在重複元素.

數組: 1 , 2 , 3 , 5 ,中不存在重複元素.

數組: 1 , 2 , 3 , 5 , 3 , 5 ,中存在重複元素.

數組: 0 , 0 , 1 , 2 , 3 , 5 , 56 , 534 , 78 , 32 ,中存在重複元素.

三、使用點陣圖法進行整形數組排序

package com.heyang;

public class BitmapSorter {

public static void main(String[] args) {

int [] arr = { 1 , 7 , - 3 , 0 , 0 , 6 , 6 , 9 , - 11 } ;

bitmapSort(arr);

for ( int i:arr) {

System.out.print(i + " , " );

}

}

public static void bitmapSort( int [] arr) {

// 找出數組中最值

int max = arr[ 0 ];

int min = max;

for ( int i:arr) {

if (max < i) {

max = i;

}

if (min > i) {

min = i;

}

}

// 得到點陣圖數組

int [] newArr = new int [max -min + 1 ];

for ( int i:arr) {

int index = i - min;

newArr[index] ++ ;

}

// 重整arr中的元素

int index = 0 ;

for ( int i = 0 ;i

while (newArr[i] > 0 ) {

arr[index] = i + min;

index ++ ;

newArr[i] -- ;

}

}

}

}

四、點陣圖法存數據

在 8K 位元組的內存空間內，如何存 unsigned short 類型數據？

一般做法：

定義一個數組： unsigned shortarrNormal[4096];

這樣做，最多只能存 4K 個 unsigned short 數據。

利用點陣圖法：

定義一個數組： unsigned chararrBit[8192];

這樣做，能存 8K*8=64K 個 unsigned short 數據。

rrBit 存放的位元組位置和位位置（位元組 0~8191 ，位 0~7 ）

比如寫 1234 ，位元組序： 1234/8 = 154; 位序： 1234 &0b111 = 2 ，那麼 1234 放在 arrBit 的下標 154 位元組處，把該位元組的 2 號位（ 0~7）置為 1

位元組位置： int nBytePos =1234/8 = 154;

位位置： int nBitPos = 1234 & 7 = 2;

// 把數組的 154 位元組的 2 位置為 1

unsigned short val = 1<

arrBit[nBytePos] = arrBit[nBytePos] |val; // 寫入 1234 得到arrBit[154]=0b00000100

此時再寫入 1236 ，

位元組位置： int nBytePos =1236/8 = 154;

位位置： int nBitPos = 1236 & 7 = 4

.// / 把數組的 154 位元組的 4 位置為 1

val = 1<

arrBit[nBytePos] = arrBit[nBytePos] |val; // 再寫入 1236 得到arrBit[154]=0b00010100

讀數據元素：按位讀取 arrBit ，取得位為 1 的位元組位置和位位置。元素值為 8*nBytePos + nBitPos

for (i=0; i<8192; i++)

{

for (j=0; j<8; j++)

{

if (arrBit[i] & (1<

{

cout <<"arrBit:" << i << " " << j <<" " << 8*i+j <

}

}

}

會輸出：

arrBit:154 2 1234

arrBit:154 4 1236

刪除元素：計算待刪除元素的位元組位置和位位置：arrBit[nBytePos] &= ~(1<< nBitPos);

比如刪除 1234 ： arrBit[154] &= ~(1<<2);

基本信息

中文名

點陣圖法

外文名

bitmap

別名

bitmap

適用範圍

大規模數據，數據狀態又不多

作用

判斷某個數據存不存在

• 目錄

目錄