|
3 | 3 | --- |
4 | 4 |
|
5 | 5 | -##Question: |
| 6 | +>Design a HashSet without using any built-in hash table libraries. |
| 7 | +>>Implement`MyHashSet` class: |
| 8 | +-`void add(key)` Inserts the value`key` into the HashSet. |
| 9 | +-`bool contains(key)` Returns whether the value`key` exists in the HashSet or not. |
| 10 | +-`void remove(key)` Removes the value key in the HashSet. If`key` does not exist in the HashSet, do nothing. |
| 11 | + |
| 12 | +--- |
| 13 | + |
| 14 | +>>Example : |
| 15 | +
|
| 16 | +MyHashSet myHashSet = new MyHashSet(); |
| 17 | +myHashSet.add(1); // set = [1] |
| 18 | +myHashSet.add(2); // set = [1, 2] |
| 19 | +myHashSet.contains(1); // return True |
| 20 | +myHashSet.contains(3); // return False, (not found) |
| 21 | +myHashSet.add(2); // set = [1, 2] |
| 22 | +myHashSet.contains(2); // return True |
| 23 | +myHashSet.remove(2); // set = [1] |
| 24 | +myHashSet.contains(2); // return False, (already removed) |
| 25 | + |
| 26 | +--- |
| 27 | +-##Solution: |
| 28 | +**Code :** |
| 29 | + |
| 30 | +```cpp |
| 31 | +classMyHashSet { |
| 32 | + public: |
| 33 | + /** Initialize your data structure here.*/ |
| 34 | + MyHashSet() : set(1000001) {} |
| 35 | + |
| 36 | + void add(int key) { |
| 37 | + set[key] = true; |
| 38 | + } |
| 39 | + |
| 40 | + void remove(int key) { |
| 41 | + set[key] = false; |
| 42 | + } |
| 43 | + |
| 44 | + /** Returns true if this set contains the specified element*/ |
| 45 | + bool contains(int key) { |
| 46 | + return set[key]; |
| 47 | + } |
| 48 | + |
| 49 | + private: |
| 50 | + vector<bool> set; |
| 51 | +}; |
| 52 | +``` |
| 53 | +- Time Complexity : O(1) |
| 54 | +- Space Complexiy : O(n) |
| 55 | +
|
| 56 | +--- |
| 57 | +Reference : [Twchen gitbook](https://twchen.gitbook.io/leetcode/) |