705. 设计哈希集合

难度简单40

不使用任何内建的哈希表库设计一个哈希集合

具体地说，你的设计应该包含以下的功能

  • add(value)：向哈希集合中插入一个值。
  • contains(value) ：返回哈希集合中是否存在这个值。
  • remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例:

1
2
3
4
5
6
7
8
9
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         
hashSet.add(2);         
hashSet.contains(1);    // 返回 true
hashSet.contains(3);    // 返回 false (未找到)
hashSet.add(2);          
hashSet.contains(2);    // 返回 true
hashSet.remove(2);          
hashSet.contains(2);    // 返回  false (已经被删除)

注意：

  • 所有的值都在 [0, 1000000]的范围内。
  • 操作的总数目在[1, 10000]范围内。
  • 不要使用内建的哈希集合库。

通过次数11,949

提交次数21,319

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class MyHashSet {
private:
    struct Node{
        int val;
        Node* next;
        Node(int val):val(val),next(nullptr){}
    };
public:
    vector<Node*> arr;
    const int len=101;
    /** Initialize your data structure here. */
    MyHashSet() {
        arr=vector<Node*>(len,new Node(-1));

    }
    
    void add(int key) {
        int addr=key%len;
        Node*temp=arr[addr];
        if(temp->val!=-1){
            while(temp){
                if(temp->val==key)return;
                if(!(temp->next)){
                    Node*node=new Node(key);
                    temp->next=node;
                    return;
                }
                 temp = temp -> next;
            }
        }else{
            temp->val=key;
            return;
        }
    }
    
    void remove(int key) {
//         int haval = key % len;
//         Node* temp = arr[haval];
//         if(temp -> val != -1){
//             while(temp){
//                 if(temp -> val == key){
//                     temp -> val = -1;
//                     return;
//                 }
//                 temp = temp -> next;
//             }
//         }
        int addr=key%len;
        Node*temp=arr[addr];
        if(temp->val!=-1){
            while(temp){
                if(temp->val==key){
                    temp->val=-1;
                    return;
                }
                temp=temp->next;
            }
        }
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        int addr=key%len;
       Node* temp=arr[addr];
        if(temp->val!=-1){
            while(temp){
                if(temp->val==key){
                    return true;
                }
                temp=temp->next;
            }
            return false;
        }else{
            return false;
        }

    }
};