問(wèn)題：已知有n整個(gè)整數(shù)，這些整數(shù)的范圍是[0, 100]，

請(qǐng)你設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，使用數(shù)組存儲(chǔ)這些數(shù)據(jù)，并提供兩種方法，分別是addMember 和 isExist。

方案一：數(shù)組直接存儲(chǔ)，遍歷查找

function FindClass() {
    let datas = [];

    // 加入一個(gè)整數(shù) member
    this.addMember = function (member) {
        datas.push(member);
    };

    // 判斷member是否存在
    this.isExist = function (member) {
        for (var i = 0; i < datas.length; i++) {
            if (datas[i] == member) {
                return true;
            }
        }
        return false;
    };
}

方案二：數(shù)字作為數(shù)組索引存儲(chǔ)，查到時(shí)速度快，但會(huì)占用更多的內(nèi)存。

function FindClass() {
    let datas = [];

    this.addMember = function (member) {
        datas[member] = true;
    };

    this.isExist = function (member) {
        return !!datas[member];
    };
}

方案三：bitmap

前置知識(shí)： 位運(yùn)算

按位與 &

相同二進(jìn)制位的數(shù)字都是1，則結(jié)果為1，其它情況都為0

如1 & 5 = 1

二進(jìn)制    整數(shù)
0 0 1     1
1 0 1     5

0 0 1     1

按位或 |

相同二進(jìn)制位的數(shù)字都是0，則結(jié)果為0，其它情況都為1

如1 | 5 = 5

二進(jìn)制    整數(shù)
0 0 1     1
1 0 1     5

1 0 1     5

左移 <<

二進(jìn)制向左移動(dòng) n 位，在后面添加 n 個(gè)0，運(yùn)算優(yōu)先級(jí)大于按位與 &和按位或 |
如3<<1 = 6

二進(jìn)制   整數(shù)
0 1 1    3

1 1 0    6

關(guān)于問(wèn)題，可以用二進(jìn)制的0和1表示數(shù)字是否存在

比如: 00001001 表示0和3存在，它代表的十進(jìn)制數(shù)是9

0 0 0 0 1 0 0 1 //二進(jìn)制
7 6 5 4 3 2 1 0 //對(duì)應(yīng)的數(shù)字是否存在

一個(gè)整數(shù)是32位，可以表示0~31是否存在。

則可以建立以下數(shù)組，相比直接用長(zhǎng)度為320的數(shù)組保存320個(gè)數(shù)字是否存在，空間省去了十分之一。

datas[0]  表示0~31存在與否
datas[1]  表示32~63存在與否
....
datas[9]  表示288~319存在與否

BitMap實(shí)現(xiàn)

function BitMap(size) {
    let datas = new Array(size).fill(0);

    this.addMember = function (member) {
        let index = Math.floor(member / 32) //在數(shù)組的索引，如2在數(shù)組索引為0的位置。
        let bit = member % 32 //在二進(jìn)制數(shù)的位置，如2在bit的索引為2的位置。
        datas[index] = datas[index] | 1 << bit // 1<<2為00100， xx0xx|00100為xx1xx
    };s

    this.isExist = function (member) {
        let index = Math.floor(member / 32)
        let bit = member % 32
        return (datas[index] & 1 << bit) !== 0 // 1<<2為00100， xxxxx&00100為00100或00000
    };
}