每日一题705 hashset的实现
文章目录
705. 设计哈希集合
实现 MyHashSet 类:
void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。
思路1
- 直接使用的c++的内置函数
unordered_set实现的(set也可以) 直接调用set的相关函数
find(key)判断是否有key元素erase(it)移除it指向的元素insert(key)插入关键字为key的元素
class MyHashSet {
public:
/** Initialize your data structure here. */
set<int> us;//内部是红黑树
MyHashSet() {
}
void add(int key) {
us.insert(key);
}
void remove(int key) {
auto it = us.find(key);
if (it != us.end()) {
us.erase(it);
}
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
if (us.find(key) != us.end()) {
return true;
} else {
return false;
}
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
*/思路2
- 使用超大数组
0 <= key <= 10^6只要数组长度>10^6,就可以实现o(1)的添加、删除时间复杂度- 但是空间复杂度太高了
class MyHashSet {
public:
/** Initialize your data structure here. */
vector<int> res;
MyHashSet() {
res.resize(1000001);
}
void add(int key) {
res[key] = 1;
}
void remove(int key) {
res[key] = 0;
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
return res[key] == 0 ? false : true;
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
*/思路3
- 拉链法减少冲突
- 使用map,key为元素哈希之后的下标,value为实际key,用set存储(防止重复元素)
class MyHashSet {
public:
/** Initialize your data structure here. */
map<int, set<int>> res;
MyHashSet() {
}
int hash(int key) {
return key % 1009;
}
void add(int key) {
int t = hash(key);
res[t].insert(key);
}
void remove(int key) {
int t = hash(key);
if (res[t].count(key) == 0) {
return;
} else {
res[t].erase(key);
}
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
int t = hash(key);
if (res[t].count(key) == 0) {
return false;
} else {
return true;
}
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
*/
set的介绍
- set内部数据结构是红黑树,作为一种关联容器,按照关键字进行查找
- set的每个元素都是有序排列的
- set的元素值唯一,不允许有重复元素
unordered_set的介绍
- unordered_set 采用数据结构是哈希表
- 元素无序排列
- 关键字唯一
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论