Go语言题解LeetCode705设计哈希集合
作者:刘09k11 发布时间:2024-03-19 22:30:38
标签:Go,LeetCode,设计,哈希集合
题目描述
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
0
投稿
猜你喜欢
- 自定义路径转换器有时候上面的内置的url转换器并不能满足我们的需求,因此django给我们提供了一个接口可以让我们自己定义自己的url转换器
- ①. vscode的常用快捷键列表1.注释:a) 单行注释:[ctrl+k,ctrl+c] 或 ctrl+/b) 取消单行注释:[ctrl+
- 一、变量1.变量Python 中的变量不需要声明。每个变量在使用前都必须赋值,变量赋值以后该变量才会被创建。在 Python 中,变量就是变
- 1. 介绍torch.norm()是对输入的tensor求对应的范数。tensor的范数有以下三种:1.1 p-范数1.2 Frobeniu
- python的set和其他语言类似, 是一个无序不重复元素集, 基本功能包括关系测试和消除重复元素. 集合对象还支持union(联合), i
- 由于我个人电脑装的Excel是2016版本的,所以这地方我使用了XSSF 方式导入 。1 先手要制定一个Excel 模板 把模板放入java
- 这篇文章主要介绍了Python3打包exe代码2种方法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,
- 来源:在工作过程中,需要统计一些trace信息,也就是一些打点信息,而打点是通过关键字进行的,因此对一个很大的文件进行分析时,想把两个打点之
- 前言作为一个数据分析师,应该信奉一句话——“一图胜千言”。不过这里要说的并不是数据可视化,而是一款全民向的产品形态——表情包!!!!表情包不
- 本文实例为大家分享了windows10更换mysql8.0.17的具体步骤,供大家参考,具体内容如下下载windows版本mysql解压后创
- 安装前的准备1.python的安装和配置在Window下:在开始菜单中找到运行输入cmd或直接搜索cmd点击进入,输入python,如果出现
- module Main whereimport Network.Socketimport Control.Concurrentmain ::
- 有个帖子写的检查全角的 <script> fun
- 串口通信是指外设和计算机间,通过数据信号线 、地线、控制线等,按位进行传输数据的一种通讯方式。这种通信方式使用的数据线少,在远距离通信中可以
- 第一种方法:采用git命令操作1、例如仓库中有下面的代码(版本1)2、现在继续编写代码,并且提交到远程仓库中(版本2)3、回退到版本1中gi
- 一、Mock介绍1、什么是Mock模拟接口接口Mock测试:在接口测试中,对于某些不容易构造或者不容易获取的接口,可以用一个模拟接口来代替2
- 本文所述实例为Python用3行代码实现解一元一次方程,代码简洁高效,具体用法如下:>>> solve("x -
- 高考在即,笔者想为孩子以后能够快乐学习数学、学习编程找到一个比较合适的项目,经过一番比较发现github上的万星项目manim(https:
- 开始制作符合标准的站点,第一件事情就是声明符合自己需要的DOCTYPE。查看本站首页原代码,可以看到第一行就是:<!DOCTYPE h
- 最近在公司的项目开发中使用到了 laravel 框架,采用的是前后端开发的模式。接触过前后端开发模式的小伙伴应该都知道,后端返回的数据格式需