leetcode705设计哈希集合

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
思路：

1.  直接开个超大数组

代码

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;
        }
    };

1.  拉链法 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;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20221005/676c68cdde2e4f3ba9b8a22b3b751edb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20221005/dea8981c402a4edda90008fcc0cb9d52.png