溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
引子：
給40億個不重復(fù)的無符號整數(shù)，沒排過序，給一個無符號整數(shù)，如何判斷這個數(shù)是否在這40億個數(shù)中。
分析：1 字節(jié)=8位
1 KB =1024字節(jié)=2^10字節(jié)
1 MB =1024KB
1 GB =1024MB
40億個數(shù)，40億可以約看為2^32，即需要將近4G的空間存儲，，如果內(nèi)存夠的話，40億個整數(shù)使用位圖存儲需要500M的空間
位圖即每一個位存儲，如果這個數(shù)存在，則先找到這個字節(jié)大小，再將字節(jié)的這個位置1
template<class T>
class BitMap
{
public:
BitMap(size_t n)
:_size(0)
{
_a.resize((n>>5)+1);//map存儲數(shù)據(jù)時是按位存儲，n>>5即n/32
}
void set(size_t x)//置位
{
size_t index = x >> 5;//即x/32
size_t num = x % 32;
if ((_a[index] & (1 << num)) == 0)//先判斷當(dāng)前位是否已被置1，若還沒被置1，則_size++且置1
{
_size++;
_a[index] |= (1 << num);
}
}
void Reset(size_t x)//取消置位
{
size_t index = x >> 5;
size_t num = x % 32;
if ((_a[index] & (1 << num)) != 0)//若當(dāng)前位不為0則_size--后置0
{
_size--;
_a[index] &= ~(1 << num);
}
}
int test(size_t x)
{
size_t index = x >> 5;
size_t num = x % 32;
return _a[index] & (1 << num);
}
private:
vector<T>_a;
size_t _size;
};未完待續(xù)
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼