Go语言题解LeetCode705设计哈希集合
作者:刘09k11 时间:2024-03-19 22:30:38
题目描述
705. 设计哈希集合
不使用任何内建的哈希表库设计一个哈希集合(HashSet)。
实现 MyHashSet 类:
void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。 示例:
输入:
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出:
[null, null, null, true, false, null, true, null, false]
解释:
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ,(未找到)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ,(已移除)
提示:
0 <= key <= 10^6
最多调用 10^4 次 add、remove 和 contains
思路分析
实现使用了链地址法,解决哈希冲突方法使用了模取余的方法(较简单的)。
这里说下为什么大家说模最好取质数,我的理解是取质数可以让取余后的结果更加均匀,以减少冲突。
举个例子,假如我们取4为模,那么虽然理论上我们应该会让数字均匀落入4个桶中,但是对于下边这个数组:
1,3,5,7,9
所有数字都落入了1,3两个桶中,造成了极大的不均,导致哈希冲突发生频繁。对于一个合数,只要我们构造合数倍数相关的数组,就很容易使哈希冲突变多,所以尽量选用质数。
AC 代码
struct Listnode{
int val;
Listnode* next = nullptr;
Listnode()=default;
Listnode(int val){
this->val = val;
}
};
class MyHashSet {
public:
/** Initialize your data structure here. */
const int prime = 991;
vector<Listnode*> nodes;
MyHashSet(): nodes(prime, nullptr){
}
void add(int key) {
if(nodes[key%prime] == nullptr){
nodes[key%prime] = new Listnode(key);
}else{
Listnode* node = nodes[key%prime];
while(node != nullptr){
if(node->val == key)return;
node = node->next;
}
node = new Listnode(key);
node->next = nodes[key%prime];
nodes[key%prime] = node;
}
}
void remove(int key) {
Listnode* prenode = nodes[key%prime];
if(prenode != nullptr && prenode->val == key){
if(prenode->next != nullptr){
nodes[key%prime] = prenode->next;
delete prenode;
}else{
delete prenode;
nodes[key%prime] = nullptr;
}
return;
}
while(prenode != nullptr && prenode->next != nullptr){
if(prenode->next->val == key){
Listnode* temp = prenode->next;
prenode->next = prenode->next->next;
delete temp;
return;
}
prenode = prenode->next;
}
}
/** Returns true if this set contains the specif ied element */
bool contains(int key) {
Listnode* node = nodes[key%prime];
while(node != nullptr){
if(node->val == key)return true;
node = node->next;
}
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);
*/
来源:https://juejin.cn/post/7179208586210312251
标签:Go,LeetCode,设计,哈希集合


猜你喜欢
CI框架整合smarty步骤详解
2023-11-14 11:18:11
Navicat连接MySQL时出现的连接失败问题及解决
2024-01-16 00:22:13

对pyqt5中QTabWidget的相关操作详解
2021-12-15 16:54:54

python中面向对象的注意点概述总结
2023-10-08 09:35:11

如何用Python写一个简单的通讯录
2021-04-13 23:47:40
YOLOv5在图片上显示统计出单一检测目标的个数实例代码
2023-07-20 18:08:42

python装饰器初探(推荐)
2023-01-19 14:40:27
PHPStudy hosts文件可能不存在或被阻止打开及同步hosts失败问题
2023-06-08 10:29:10

一步步教你用python给女朋友写个微信自动提醒的程序
2022-09-03 16:50:25

django 2.2和mysql使用的常见问题
2024-01-27 17:40:02
分析MongoDB和MySQL各自的关键特性、差别和优势
2024-01-23 16:23:30

numpy中的converters和usecols用法详解
2021-01-23 18:29:29

C#处理MySql多个返回集的方法
2024-01-21 15:30:08

python pandas中的agg函数用法
2023-07-20 09:40:08

Python 登录网站详解及实例
2022-05-31 00:47:57
了解一下python内建模块collections
2022-03-19 08:32:37
python 实现一个反向单位矩阵示例
2023-07-27 16:05:51

MDF文件在SQL Server中的恢复技术
2024-01-18 16:25:48
JS实现json数组排序操作实例分析
2024-04-18 09:44:25

一空间多域名绑定不同目录方法
2009-03-09 18:32:00