- 相關(guān)推薦
數(shù)據(jù)處理面試題(3)
}
*p = *p|(0x01<<(posi%BYTESIZE));//將該Bit位賦值1
return;
}
void BitMapSortDemo()
{
//為了簡單起見，我們不考慮負數(shù)
int num[] = {3,5,2,10,6,12,8,14,9};
//BufferLen這個值是根據(jù)待排序的數(shù)據(jù)中最大值確定的
//待排序中的最大值是14，因此只需要2個Bytes(16個Bit)
//就可以了。
const int BufferLen = 2;
char *pBuffer = new char[BufferLen];
//要將所有的Bit位置為0，否則結(jié)果不可預(yù)知。
memset(pBuffer,0,BufferLen);
for(int i=0;i<9;i++)
{
//首先將相應(yīng)Bit位上置為1
SetBit(pBuffer,num[i]);
}
//輸出排序結(jié)果
for(int i=0;i
{
for(int j=0;j
{
//判斷該位上是否是1，進行輸出，這里的判斷比較笨。
//首先得到該第j位的掩碼(0x01<< p="">
//位和此掩碼作與操作。最后判斷掩碼是否和處理后的
//結(jié)果相同
if((*pBuffer&(0x01<
{
printf("%d ",i*BYTESIZE + j);
}
}
pBuffer++;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
BitMapSortDemo();
return 0;
}
可進行數(shù)據(jù)的快速查找，判重，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下
基本原理及要點
使用bit數(shù)組來表示某些元素是否存在，比如8位電話號碼
擴展
Bloom filter可以看做是對bit-map的擴展(關(guān)于Bloom filter，請參見：海量數(shù)據(jù)處理之Bloom filter詳解)。
問題實例
1)已知某個文件內(nèi)包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。
8位最多99 999 999，大概需要99m個bit，大概10幾m字節(jié)的內(nèi)存即可。 (可以理解為從0-99 999 999的數(shù)字，每個數(shù)字對應(yīng)一個Bit位，所以只需要99M個Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內(nèi)存表示了所有的8位數(shù)的電話)
2)2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)。
將bit-map擴展一下，用2bit表示一個數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上，在遍歷這些數(shù)的時候，如果對應(yīng)位置的值是0，則將其置為1;如果是1，將其置為2;如果是2，則保持不變�；蛘呶覀儾挥�2bit來進行表示，我們用兩個bit-map即可模擬實現(xiàn)這個2bit-map，都是一樣的道理。
【數(shù)據(jù)處理面試題(3)】相關(guān)文章：
Microsoft面試題09-04
iOS面試題07-10
公司面試題09-12
hibernate面試題10-18
英語面試題精選06-13
小升初面試題06-10
PHP面試題10-14
IT行業(yè)有關(guān)數(shù)據(jù)處理的英文求職信09-25
小升初面試題型08-24