1013: 哈希表(开放定址法处理冲突)

解法:

线性探测是一种解决哈希冲突的方法,当发生哈希冲突时,它会依次往后查找空的槽位,直到找到一个空的槽位或者达到数组的末尾。

下面是处理哈希冲突的线性探测的步骤:

  1. 创建一个哈希表,里面包含一定数量的槽位。
  2. 当需要插入一个新的元素时,计算它的哈希值,得到一个位置,如果该位置为空,则直接将元素插入到该位置。
  3. 如果计算得到的位置已经被占用,发生了哈希冲突,那么就从当前位置开始往后查找,直到找到一个空的槽位或者达到数组的末尾。
  4. 将元素插入到找到的空的槽位中。
  5. 当需要查找一个元素时,首先计算它的哈希值,得到一个位置,如果该位置处的元素与要查找的元素相等,则返回该元素。
  6. 如果计算得到的位置处的元素与要查找的元素不相等,那么就从该位置开始往后查找,直到找到要查找的元素或者找到一个空的槽位或者达到数组的末尾。
  7. 如果找到要查找的元素,则返回该元素,否则表示没有找到。

需要注意的是,线性探测可能会导致哈希表的填装因子过高,从而影响性能。因此,当哈希表中的槽位被占用的比例达到一个阈值时,可以考虑进行扩容,重新哈希所有的元素,以保持哈希表的性能。

用-1初始化表明该位置为空。

#include<iostream>
#include<vector>
using namespace std;
void find(vector<int>& a) {
	int x;
	cin >> x;
	int pos = x % a.size();
	int cnt = 0;
	for (int i = pos; i < a.size(); i++) {
		cnt++;
		if (x == a[i]) {
			cout << pos << "," << cnt;
			return;
		}
	}
	cout << -1;
}
int main() {
	int m, n, a;
	cin >> m >> n;
	vector<int> vec(m,-1);
	for (int i = 0; i < n; i++) {
		cin >> a;
		int pos = a % m;
		if (vec[pos] == -1) vec[pos] = a;
		else {
			int sta = pos + 1;
			while (vec[sta] != -1&&sta<m) {
				sta++;
			}
			vec[sta] = a;
		}
	}
	find(vec);
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/610498.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Ps 滤镜:视频

Ps菜单&#xff1a;滤镜/视频 Filter/Video “视频”滤镜子菜单中包含了“NTSC 颜色”和“逐行”两个滤镜。 这两个滤镜都是针对视频和电视播放的特定需求设计的。 “逐行”滤镜主要解决交错视频的视觉问题&#xff0c;而“NTSC 颜色”滤镜则确保色彩在电视播放时的兼容性和准确…

一文带你了解OSPF 七种LSA类型,很全!

大家好&#xff0c;今天我们 带大家了解一下OSPF的七种LSA类型。 在OSPF&#xff08;开放式最短路径优先&#xff09;协议中&#xff0c;LSA&#xff08;链路状态通告&#xff09;是一种至关重要的数据格式&#xff0c;专门用于描述路由信息。它包含了路由器或网络的各种状态信…

编写一个C#程序,实现音乐文件的播放功能

一、作业要求 要求1&#xff1a; 1. 程序应能够读取MP3文件&#xff0c;并播放其中的音频。 2. 程序应能够处理可能出现的异常&#xff0c;如文件不存在、文件读取错误等。 3. 程序应具有良好的用户界面&#xff0c;方便用户进行操作。 4. 程序应具有良好的兼容性&#xf…

VK6932 SOP32数码屏驱动IC抗干扰数显芯片高稳定LED驱动 原厂FAE支持

产品型号&#xff1a;VK6932 产品品牌&#xff1a;永嘉微电/VINKA 封装形式&#xff1a;SOP32 工程服务&#xff0c;技术支持&#xff01; 概述 VK6932是一种数码管或点阵LED驱动控制专用芯片&#xff0c;内部集成有3线串行接口、数据锁存器、LED 驱动等电路。SEG脚接LED阳…

【Python】selenium爬虫常见用法和配置,以及常见错误和解决方法

欢迎来到《小5讲堂》 这是《Python》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 前言无执行文件代码报错信息错误路径手动下载自动下载 选项配置Ch…

js之遍历方法

先创建一个数组&#xff0c;然后使用for.in进行遍历&#xff0c;如下图所示sub代表下标并且遍历几次&#xff0c;arr代表数组 <script>let arr [1, 2, 3, 4, 5, 6];for (let sub in arr) {console.log(arr);}</script> 第二种方法则是for循环遍历&#xff0c;根据…

Transformer 解析 超级详细版

推荐学习视频 汉语自然语言处理-从零解读碾压循环神经网络的transformer模型(一)- 注意力机制-位置编码-attention is all you need_哔哩哔哩_bilibili 目录 首先下transformer和LSTM的最大区别是什么&#xff1f; 1.positional \ encoding, 即位置嵌入(或位置编码); 2 自注…

windows连接CentOS数据库或Tomcat报错,IP通的,端口正常监听

错误信息 数据库错误&#xff1a; ERROR 2003 (HY000): Cant connect to MySQL server on x.x.x.x (10060) Tomcat访问错误&#xff1a; 响应时间过长 ERR_CONNECTION_TIMED_OUT 基础排查工作 【以下以3306端口为例&#xff0c;对于8080端口来说操作是一样的&#xff0c;只需…

NM2-WRDUW施耐德电动机保护器EOCR-NM2

EOCR智能电动机保护器原产地为韩国&#xff0c;隶属于施耐德(韩国)电气有限公司工厂。此公司早起源于韩国三和SAMWHA株式会社&#xff0c;是早研发电子式电动机保护器厂家&#xff0c;产品涵盖过电流继电器EOCR-SS,EOCR-SE2,EOCR-AR&#xff0c;欠电流继电器EUCR&#xff0c;数…

3分钟快速了解VR全景编辑器

说到VR全景&#xff0c;想必大多数人都见过那种可以360旋转拖动观看的图片。虽然这种技术已经不算新鲜&#xff0c;如果你以为这就是VR全景的全部&#xff0c;那就大错特错了&#xff01; 上面看到的这种形式&#xff0c;只能算VR全景的第一层形态。现在的VR全景已经发展成为了…

LabVIEW自动机械变速器(AMT)开发

LabVIEW自动机械变速器&#xff08;AMT&#xff09;开发 在现代汽车工业中&#xff0c;提升车辆的自动化水平和驾驶体验是一个不断追求的目标。随着技术的发展&#xff0c;自动机械变速器&#xff08;AutomatedMechanical Transmission, AMT&#xff09;凭借其较高的能效和较低…

四、VGA项目:联合精简帧+双fifo+sobel算法 实现VGA显示

前言&#xff1a;该项目实际上是在很多基础的小练习上合成起来的&#xff0c;例如涉及到uart&#xff08;rs232&#xff09;的数据传输、双fifo流水线操作、VGA图像显示&#xff0c;本次内容在此基础上又增添了sobel算法&#xff0c;能实现图像的边沿监测并VGA显示。 文章目录…

你写的每条SQL都是全表扫描吗

你写的每条SQL都是全表扫描吗&#xff1f;如果是&#xff0c;那MySQL可太感谢你了&#xff0c;每一次SQL执行都是在给MySQL上压力、上对抗。MySQL有苦难言&#xff1a;你不知道索引吗&#xff1f;你写的SQL索引都失效了不知道吗&#xff1f;慢查询不懂啊&#xff1f;建那么多索…

Xinstall助力App地推监测,实现精准效果评估

在移动互联网时代&#xff0c;App的推广已经成为企业营销的重要手段。然而&#xff0c;如何有效地监测App地推效果&#xff0c;一直是广告主和开发者面临的难题。幸运的是&#xff0c;Xinstall作为国内专业的App全渠道统计服务商&#xff0c;为广告主和开发者提供了一站式的解决…

【C++阅览室】C++之Vector(容器)

目录 vector的介绍 vector的使用 vector的定义 vector iterator 的使用 vector 空间增长问题 vector 增删查改 vector 迭代器失效问题。&#xff08;重点&#xff09; vector的介绍 1、 vector 是表示可变大小数组的序列容器&#xff0c;可以使用连…

java.lang.NoSuchMethodException: com.ruoyi.web.controller.test.bean.HeadTeacher

软件开发过程中使用Java反射机制时遇到了下面的问题 com.ruoyi.web.controller.test.bean.HeadTeacher4b9af9a9 com.ruoyi.web.controller.test.bean.HeadTeacher4b9af9a9java.lang.NoSuchMethodException: com.ruoyi.web.controller.test.bean.HeadTeacher.<init>(java…

英飞凌TC3xx 启动逻辑梳理(1)

目录 1.启动时序总览 2.Boot Firmware干了什么&#xff1f; 2.1 BMHD梳理 2.2 HWCFG 2.3 ABM 2.4 BMHD 无效时处理方案 2.5 HSM启动如何影响SSW启动 3.小结 在调TC3xx的板子时&#xff0c;最害怕的就是刷UCB&#xff1b;稍不注意板子就上锁&#xff0c;调试器也连不上了…

MacOS java多版本安装与管理

Home - SDKMAN! the Software Development Kit Manager # 安装sdkman curl -s "https://get.sdkman.io" | bashsource "$HOME/.sdkman/bin/sdkman-init.sh"sdk version正常出现sdkman版本号就安装成功了 # 安装java # 安装java8 sdk install java 8.0…

大数据------JavaWeb------Tomcat(完整知识点汇总)

Web服务器——Tomcat Web服务器定义 它是一个应用程序&#xff08;软件&#xff09;&#xff0c;对HTTP协议的操作进行封装&#xff0c;使得程序员不必直接对协议进行操作&#xff0c;让Web开发更便捷 Web服务器主要功能 封装HTTP协议操作&#xff0c;简化开发将Web项目部署到…

浅谈如何自我实现一个消息队列服务器(7)——编写服务器部分

文章目录 一、编写服务器代码1.1、分析一个服务器应具备的功能1.1.1、成员变量1.1.2、对外提供的接口 一、编写服务器代码 再次拿出这张图&#xff0c;前面我们已经将重要概念&#xff1a;VirtualHost、exchange、msgQueue、message、binding 都实现了&#xff0c;此时就可以开…
最新文章