2166. 設計位集

思路

判斷某些數字是否出現時，最直接的想法是使用哈希表。
比如現在出現數字 35，就將哈希表標註為true代表有出現過，也就是umap[35] = true。
雖說複雜度是 $O(1)$，但是這個「常數時間」比較花時間（大多情況都比位運算慢）。

現在有一串二進制 $1100100$，從左到右看，第零、一、四位是 1，也就代表數字0, 1, 4 出現過。
用二進制去紀錄數字有沒有出現過，就是位圖在做的事情。
相比於哈希表，它的常數操作比較快，缺點在於需要事先知道數字範圍，而且若範圍太大就不適合使用。

假如現在出現數字 35，就將二進制的第 35 個位元標註為 1，代表有出現過。
每個int數字一共有 32 個位元，假如現在有四個數 $\text{a, b, c, d}$

• a 能用來記錄數字 0 ~ 31 是否有出現過。
• b 能用來記錄數字 32 ~ 63 是否有出現過。
• c 能用來記錄數字 64 ~ 95 是否有出現過。
• d 能用來記錄數字 96 ~ 127 是否有出現過。

現在的數字 35，想要知道紀錄應該放在第幾個數的第幾個位元中，將它 / 32與 % 32就能得知。

• $35~/~32=1$，應該放在第一個數字 $b$（從第 0 個位置開始算。）
• $35~\%~32 = 3$，在數字 $b$ 當中的第三個位置。（從第 0 個位置開始算。）

程式碼

位圖

class Bitset {
private:
    const int LEN = 32;
    vector<int> bset;
    int size, cnt;
    bool isFlip = false;
public:
    Bitset(int n) : bset((n + LEN - 1) / LEN), size(n), cnt(0), isFlip(false) {}
    
    void fix(int idx) {
        int i = idx / LEN, j = idx % LEN;
        int bit = (bset[i] >> j) & 1;
        if(!isFlip) {
            // 維持原樣，1 表示存在，0表示不存在
            if(bit == 0) {
                ++cnt;
                bset[i] |= (1 << j);
            }
        }
        else {
            // 翻轉，1 表示不存在，0 表示存在
            if(bit == 1) {    
                ++cnt;
                bset[i] &= ~(1 << j);
            }
        }
    }
    
    void unfix(int idx) {
        int i = idx / LEN, j = idx % LEN;
        int bit = (bset[i] >> j) & 1;
        if(!isFlip) {
            // 維持原樣，1 表示存在，0表示不存在
            if(bit == 1) {
                --cnt;
                bset[i] &= ~(1 << j);
            }
        }
        else {
            // 翻轉，1 表示不存在，0 表示存在
            if(bit == 0) {    
                --cnt;
                bset[i] |= (1 << j);
            }
        }
    }
    
    void flip() {
        isFlip = !isFlip;
        cnt = size - cnt;
    }

    bool all() {
        return cnt == size;
    }
    
    bool one() {
        return cnt > 0;
    } 

    int count() {
        return cnt;
    }
    
    string toString() {
        string res;
        res.reserve(size);
        for(int i = 0; i < size; ++i) {
            int bit = (bset[i / LEN] >> (i % LEN)) & 1;
            if(!isFlip) res += (bit == 1 ? '1' : '0');
            else res += (bit == 0 ? '1' : '0');
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(1)$，toString操作 $O(n)$。
• 空間複雜度：$O(n)$