Sponsored
Sponsored
The direct address table approach is simple and efficient for this problem since the maximum key size is limited to 106. We can use a boolean array of size 106+1 where each index represents a key. The value stored at a given index indicates whether the key is present in the HashSet. This allows for O(1) time complexity for the 'add', 'remove', and 'contains' operations.
Time Complexity: O(1) for all operations (add, remove, contains).
Space Complexity: O(MAX), which is O(10^6).
1#include <stdio.h>
2#include <stdbool.h>
3
4#define MAX 1000001
5
6typedef struct {
7 bool container[MAX];
8} MyHashSet;
9
10MyHashSet* myHashSetCreate() {
11 MyHashSet* set = (MyHashSet*)malloc(sizeof(MyHashSet));
12 for(int i = 0; i < MAX; i++) {
13 set->container[i] = false;
14 }
15 return set;
16}
17
18void myHashSetAdd(MyHashSet* obj, int key) {
19 obj->container[key] = true;
20}
21
22void myHashSetRemove(MyHashSet* obj, int key) {
23 obj->container[key] = false;
24}
25
26bool myHashSetContains(MyHashSet* obj, int key) {
27 return obj->container[key];
28}
29
30void myHashSetFree(MyHashSet* obj) {
31 free(obj);
32}
33The solution creates a struct with a boolean array of size 1000001. Each index in this array corresponds to a potential key, and its boolean value represents whether that key is currently present in the set. Methods for adding, removing, and checking for keys simply modify or access this boolean array.
This approach simulates a hash set using a hash function to assign keys to buckets, dealing with potential collisions using chaining. We create an array of lists, where each list contains keys that hash to the same index. This way, operations require traversing these short lists upon collisions.
Time Complexity: O(1) average, O(n) worst-case for add, remove, and contains due to collision chains.
Space Complexity: O(n), where n is the number of keys actually added.
1#include <list>
using namespace std;
class MyHashSet {
private:
vector<list<int>> data;
static const int base = 769;
static int hash(int key) {
return key % base;
}
public:
MyHashSet() : data(base) {}
void add(int key) {
int h = hash(key);
for (int k : data[h]) {
if (k == key) return;
}
data[h].push_back(key);
}
void remove(int key) {
int h = hash(key);
data[h].remove(key);
}
bool contains(int key) {
int h = hash(key);
for (int k : data[h]) {
if (k == key) return true;
}
return false;
}
};
In C++, the solution involves a vector of lists to represent the hash set. The hash function assigns keys to buckets, and these buckets store keys using linked lists (std::list). Each operation checks for key presence, adds new keys or removes existent keys, all handled within these lists.