빅 데이터 처리 에서 흔히 볼 수 있 는 문제:통계 3 억 개의 정수 에서 나타 나 지 않 은 정수 와 중복 되 지 않 은 정수

통계 3 억 개의 정수 에 나타 나 지 않 은 정수 에 대해 서 는 비트 맵 같은 구 조 를 하나만 사용 하면 된다.
비트 맵 은 하나의 비트 배열 을 사용 하 는 것 으로 모든 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트다음은 예제 코드 입 니 다.
Set 먼저 그 배열 의 위 치 를 찾 은 다음 에 그 위치 나 이전 위치 로 갑 니 다.
 

lass BitMap
{
public:
    BitMap(size_t num)
    {
        _v.resize((num >> 5) + 1); //    num/32 + 1
    }

    void Set(size_t num) //set 1
    {
        size_t index = num >> 5; //    num/32
        size_t pos = num % 32;
        _v[index] |= (1 << pos);
    }

    void ReSet(size_t num) //set 0
    {
        size_t index = num >> 5; //    num/32
        size_t pos = num % 32;
        _v[index] &= ~(1 << pos);
    }

    bool HasExisted(size_t num)//check whether it exists
    {
        size_t index = num >> 5;
        size_t pos = num % 32;
        bool flag = false;
        if (_v[index] & (1 << pos))
            flag = true;
        return flag;

    }

private:
    vector _v;
}; 

그렇다면 중복 되 지 않 은 수 를 어떻게 찾 을 수 있 을 까?간단 합 니 다.비트 맵 두 개 를 사용 하거나 비트 두 개 로 한 수가 00 이 나 오지 않 았 다 는 것 을 표시 합 니 다.한 번 01 이 나 오고 두 번 10 이 나 오고 세 번 이상 11 이 나 옵 니 다.