【面試題】給40億個無符号不重複且沒排過序的數，查找一個數是否在這40億個數之中

看到這樣一道面試題，我們不由的想到前邊學習過的哈希表，哈希表查找效率高，唯獨就是 空間浪費有點大。而在這道題目之中，40億個無符号數（表明最高位表示大小），幾乎涵蓋了整形裡的所有的數（總共42億9千多）。而42億9千多的數全部放到記憶體大約需要4G*4 = 16G，加上作業系統，各種運作軟體，我們普通的計算機是無法運作這42億數字的，除非超級計算機。是以，按照将每個數字都占用一個整形空間的方式導入記憶體的方式是不可取的。我們知道，資料在計算機中都是以二進制格式存儲的，或0或1，我們不妨用每一個二進制位（比特位）來存儲一個數，存在的話置為1，不存在置為0，這樣的話，一個int可以表示32個數字。所有的資料會隻占用到16G/32 = 500MB，一般的計算機還是可以滿足這個請求的。40億個數字，隻能存儲到硬碟，查找的時候導入記憶體就好了。下邊給出實作代碼~~~“

#pragma once
#include<iostream>
using namespace std;
#include<vector>
class BitMap
{
public:
    BitMap(size_t range)
    {
        _tables.resize((range >> )+);
    }

    void Set(size_t num)
    {
        //确定num在第幾個數
        int index = num >> ;
        //确定num在 index的哪一位
        int pos = num % ;
        //置位
        _tables[index] |= ( << pos);
    }

    void ReSet(size_t num)
    {
        int index = num >> ;
        int pos = num % ;

        _tables[index] &= (~( << pos));
    }

    bool Test(size_t num)
    {
        int index = num >> ;
        int pos = num % ;
        return _tables[index] & ( << pos);
    }

protected:
    vector<size_t> _tables;
};

void TestBitMap()
{
    BitMap bm(-);
    bm.Set();
    bm.Set();
    bm.Set();

    cout << "100:"<<bm.Test()<<endl;
    cout << "200:"<<bm.Test()<<endl;
    cout << "800:"<<bm.Test()<<endl;
    cout << "468:"<<bm.Test()<<endl;

    bm.ReSet();


    cout << "100:"<<bm.Test()<<endl;
    cout << "200:"<<bm.Test()<<endl;
    cout << "800:"<<bm.Test()<<endl;
    cout << "468:"<<bm.Test()<<endl;
}
           

我們知道 -1 在計算機中的存儲就是 11111111 11111111 11111111 11111111，轉換成無符号數，就是 2^32-1，可以存儲整形裡的所有數字了~

上邊的代碼僅僅給出了幾個資料的置位，複位及查找，對于大資料也是一樣的。隻不過資料應該從硬碟擷取就可以了。下邊關于代碼做以詳細解釋~~

這樣我們就能很快的判斷一個數字是否在那個大資料之中了，然而對于這樣的題目，還有另外一種方法：

對于給定的一個數，我們可以很快就得出這個數的二進制表示。用這個數的每一個比特位去從大資料中篩選：比如資料的最高位是0，我們就篩選出大資料中最高位是0的數，這樣資料的多少大約就能減少一半，然後根據第二位繼續進行篩選，依次類推，32次篩選就可以判斷給定的資料是否在大資料中。這樣的方法，相較于上邊的做法還是有一定的缺陷，比如我們要查找幾個數，上邊的辦法效率還是稍微高一點的~~

關于這道題目就分析到這裡，有問題留言~~