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://xiahunao.cn/news/3030146.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Oracle数据库如何插入平方(²)立方(³)字符

第一步&#xff1a;创建数据表&#xff0c;字段一定要是NVARCHAR2类型的 第二步&#xff0c;插入数据用 unistr(1\00b3) 形式的写法 00b3 代表m&#xff0c;00b2代表㎡ SELECT * FROM TESTABC; UPDATE TESTABC set NAME1unistr(1\00b3); UPDATE TESTABC set NAME2unistr(2\00b2…

python从0开始学习(五)

目录 前言 1、顺序结构 2、选择结构 2.1双分支结构 2.2多分枝结构 2.3嵌套使用 2.4多个条件的链接 总结 前言 在上篇文章中&#xff0c;我们学习了python中的运算符&#xff0c;本篇文章继续往下讲解。本篇文章主要讲解程序的组织结构。 1、顺序结构 顺序结构是程序按照…

图片转图标(ICO)的工具软件

目前常用的ICO转换方式大多都是网页在线转换&#xff0c;没网就无法使用了。自己编写了一款小软件&#xff0c;可以将各种格式图片转为ICO图标。 目前支持PNG,BMP,JPG,JPEG,GIF等格式的图片转换成ICO&#xff0c;支持的尺寸有常用的16*16&#xff0c;24*24&#xff0c;32*32&am…

【MySQL基本查询(下)】

文章目录 一、update案例 二、Delete案例注意&#xff1a;delete 全表数据的行为慎用&#xff01;truncate 三、插入查询结果案例 四、了解一些函数1.count函数2.sum函数3. avg函数4.max函数5. min函数 五、group by子句的使用案例having和where 一、update 该关键字的功能就是…

探索 Joomla! CMS:打造个性化网站的利器

上周我们的Hostease客户咨询建站服务。他想要用Joomla建站。Hostease提供免费安装Joomla CMS服务。这可以让客户搭建网站变得更加简单和高效。下面是针对Joomla建站的一些使用心得。 Joomla CMS是一款开放自由的软件&#xff0c;为用户提供了创建和维护网站的自由度。它经过全…

单调栈:(C++)

在题目的要求中&#xff0c;存在先进后出&#xff08;即在前面的数据需要遍历到后面的某一数据时才能确定计算值&#xff09;单调栈在一部分解题场景中避免了暴力解法的高时间复杂度问题&#xff0c;但是在做题过程中视情况而定&#xff0c;有些题目的最优解不一定使用单调栈&a…

多维点分布的均匀性评估方法(NDD和Voronoi 图法)

评估多维点分布的均匀性是统计学和数据科学中的一个重要问题&#xff0c;特别是在模拟、空间分析和样本设计等领域。下面&#xff0c;我将详细介绍2种评估多维点分布均匀性的方法&#xff0c;包括它们的数学原理、实现公式以及各自的优缺点。 1. 最近邻距离法&#xff08;Neare…

复习了好久的软考中项,现在上半年不考了,该怎么办?

如果有更多学习时间的话&#xff0c;可以考虑报考高级职称&#xff0c;因为高级和中级职称的很多知识点有重叠&#xff0c;只需要再复习一下相关论文就可以了。 从2024年下半年开始&#xff0c;集成考试将采用最新版教材和大纲&#xff0c;与高级职称的新版教材内容相似度很高…

深入浅出JavaScript继承机制:解密原型、原型链与面向对象实战攻略

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 &#x1f525; 引言&#x1f9f1; 原型基础⛓️ 原型链的形成&#x1f504; 修改原型的影响&#x1f3c1; 原型链的尽头为什么null标志着结束&#xff1f;实际意义 &#x1f310; &#x1f504; 继承的实现方式1. 原型链继承…

海外仓管理系统:为什么推荐基于云的SaaS模式,而不是本地部署

海外仓管理系统 是 海外仓 企业 使用 最多 的 软件 &#xff0c; 根据 公开 的 行业 数据 显示 &#xff0c; 几乎 8 4 % 的 海外仓 企业 都会 通过 海外仓 管理系统 来 管理 仓储 。 然而&#xff0c;市场上存在很多不同类型的海外仓管理系统可以选择&#xff0c;归结起来有两…

【Web】2023浙江大学生省赛初赛 secObj 题解

目录 step 0 step 1 step 2 step 3 题目本身是不难&#xff0c;简单复健一下 step 0 pom依赖就是spring 反序列化入口在./admin/user/readObj 输入流做了黑名单的过滤&#xff0c;TemplatesImpl不能直接打 可以jackson打SignedObject二次反序列化绕过 具体原理看下面这…

哪里有视频素材可以用?全视频素材都在哪里找?

在这个数字化快速发展的世界中&#xff0c;高清和4K视频素材对于提升视觉故事的品质至关重要。以下是一系列全球知名的视频素材网站&#xff0c;它们提供的高质量素材能够满足您从商业广告到个人项目的所有需求。 1. 蛙学府 以其庞大的创意资源库著称&#xff0c;订阅者可以无…

1.基于python的单细胞数据预处理-归一化

目录 归一化的引入移位对数皮尔森近似残差两个归一化方法的总结 参考&#xff1a; [1] https://github.com/Starlitnightly/single_cell_tutorial [2] https://github.com/theislab/single-cell-best-practices 归一化的引入 在质量控制中&#xff0c;已经从数据集删除了低质…

百面算法工程师 | 传统图像处理——OpenCV

本文给大家带来的百面算法工程师是传统图像处理的面试总结&#xff0c;文章内总结了常见的提问问题&#xff0c;旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中&#xff0c;我们将介绍一些集几何变换和图像平滑处理&#xff0c;并提供参考的回答及其理论基础&…

JAVA 双亲委派之一

JAVA 双亲委派之一 JVM类加载流程 java语言系统内置了众多类加载器&#xff0c;从一定程度上讲&#xff0c;只存在两种不同的类加载器&#xff1a;一种是启动类加载器&#xff0c;此类加载由C实现&#xff0c;是JVM的一部分&#xff1b;另一种就是所有其他的类加载器&#xf…

QT作业5

1、聊天室 服务器端 //头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTcpServer> #include <QTcpSocket> #include <QList> #include <QListWidget> #include <QMessageBox> #include <QDebug> #includ…

第十五届蓝桥杯python B组省赛

前言&#xff1a; 这是我第一次参加蓝桥杯&#xff0c;成绩并不理想&#xff0c;我反思了一下午&#xff0c;我的问题主要是知识点学不透&#xff0c;题目做的太少&#xff0c;而且学习的时候少数时间不专心&#xff0c;但是&#xff0c;我能感觉到我的学习能力并不弱&#xf…

用云手机打造海外社媒矩阵

在全球经济一体化的大背景下&#xff0c;中国出海企业及B2B外贸公司正将海外社交媒体营销作为重要的市场拓展策略。为更好地触及不同受众群体&#xff0c;构建跨平台的社媒矩阵已成为企业营销的关键步骤。本文将探讨如何利用云手机技术&#xff0c;高效管理并运营多个海外社交媒…

CSS-页面导航栏实现-每文一言(过有意义的生活,做最好的自己)

&#x1f390;每文一言 过有意义的生活,做最好的自己 目录 &#x1f390;每文一言 &#x1f6d2;盒子模型 &#x1f453;外间距 (margin) &#x1f97c;边框 &#x1f45c;内边距 切换盒子模型计算方案&#xff1a; &#x1f3a2; 浮动布局 浮动特点 &#x1f3c6;导航…

Adobe Photoshop PS 25.6.0 解锁版 (最流行的图像设计软件)

前言 Adobe Photoshop 是一款专业强大的图片处理工具&#xff0c;从照片编辑和合成到数字绘画、动画和图形设计&#xff0c;一流的图像处理和图形设计应用程序是几乎每个创意项目的核心所在。利用 Photoshop 在桌面上的强大功能&#xff0c;您可以在灵感来袭时随时随地进行创作…