解法:
- 算法: 模拟哈希表, 此题用的是拉链法, 用到了vector, 并且包括删除操作
- 时间复杂度: $O(1)$ 一般哈希函数是为了把一个很大的值域映射到一个比较小的值域. 此题key值为$10^6$, 需要映射到$10^4$, 所以定义N为10003即可.
- 映射用取模实现,key%N
- 拉链借用了vector而不是手写单链表. 所以用到了push_back() 和 erase()
- find定义为bool类型也可以
const int N=10003;
class MyHashSet {
vector<int>h[N];
public:
MyHashSet() {
}
int find(vector<int>&h,int x){
for(int i=0;i<h.size();i++)
if(h[i]==x) return i;
return -1;
}
void add(int key) {
int t=key%N;
int k=find(h[t],key);
if(k==-1) h[t].push_back(key);
}
void remove(int key) {
int t=key%N;
int k=find(h[t],key);
if(k!=-1) h[t].erase(h[t].begin()+k);
}
bool contains(int key) {
int t=key%N;
int k=find(h[t],key);
return k!=-1;
}
};