leetcode705设计哈希集合-蒲公英云

leetcode705设计哈希集合

桃扇骨 2022-10-06 11:47 236阅读 0赞

在这里插入图片描述

思路：

直接开个超大数组

代码

class MyHashSet { 
private:
    int message[1000001];
public:
    /** Initialize your data structure here. */
    MyHashSet() { 
        for(auto &a:message)
            a=0;
    }
    void add(int key) { 
        if(message[key]==0)
            message[key]=1;
    }
    void remove(int key) { 
        if(message[key])
            message[key]=0;
    }
    /** Returns true if this set contains the specified element */
    bool contains(int key) { 
        if(message[key])
            return true;
        return false;
    }
};

拉链法 list超时了

class MyHashSet {
private:

int base = 1023;
vector<list<int>> messages;//这不能初始化

public:

int hash(int key){ 
    return key%base;
}
/** Initialize your data structure here. */
MyHashSet() //:messages(base)
{ //只有在这个地方才能初始化
    messages.resize(base);
}
void add(int key) { 
    int num = hash(key);
    for(auto a = messages[num].begin();a!=messages[num].end();a++){ 
        if(*a==key)
            return;
    }
    messages[num].push_back(key);
}
void remove(int key) { 
    int num = hash(key);
    for(auto a = messages[num].begin();a!=messages[num].end();){ 
        if(*a==key){ 
            a = messages[num].erase(a);
            return;
        }
        else a++;
    }
}  
/** Returns true if this set contains the specified element */
bool contains(int key) { 
    int num = hash(key);
    for(auto a = messages[num].begin();a!=messages[num].end();){ 
        if(*a==key)
            return true;
    }
    return false;
}