代码训练LeetCode(17)存在重复元素
代码训练(17)LeetCode之存在重复元素
Author: Once Day Date: 2024年5月7日
漫漫长路,才刚刚开始…
全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客
参考文章:
- 219. 存在重复元素 II - 力扣(LeetCode)
- 力扣 (LeetCode) 全球极客挚爱的技术成长平台
文章目录
- 代码训练(17)LeetCode之存在重复元素
- 1. 原题
- 2. 分析
- 3. 代码实现
- 4. 总结
1. 原题
给你一个整数数组
nums和一个整数k,判断数组中是否存在两个 不同的索引i和j,满足nums[i] == nums[j]且abs(i - j) <= k。如果存在,返回true;否则,返回false。
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^90 <= k <= 10^5
例如对于nums = [1,2,3,1,2,3], k = 2,不存在间隔两个以内的相等值,因此返回False。
2. 分析
该题目要求我们判断一个给定的整数数组 nums 中是否存在两个不同的索引 i 和 j,使得 nums[i] == nums[j] 且两个索引的差的绝对值不大于 k。如果存在这样的一对索引,则返回 true,否则返回 false。
要解决这个问题,可以采用哈希表记录法:
- 创建一个哈希表来存储数组值和其对应的最新索引。
- 遍历数组,对于每个元素,检查哈希表中是否已经存在该元素:
- 如果存在,则比较当前索引与哈希表中存储的索引的差的绝对值是否不大于
k。 - 如果满足条件,则直接返回
true。 - 如果不满足条件,或者元素不存在于哈希表中,则更新哈希表,将该元素的索引设置为当前索引。
- 如果存在,则比较当前索引与哈希表中存储的索引的差的绝对值是否不大于
- 如果遍历完数组后没有找到符合条件的元素对,则返回
false。
分析步骤:
- 初始化一个空的哈希表
map。 - 遍历数组
nums,对于每个元素nums[i]:- 检查
nums[i]是否已存在于map中。 - 如果存在,计算当前索引
i和map[nums[i]]的差的绝对值。 - 如果这个差值小于等于
k,返回true。 - 否则,更新
map[nums[i]]为当前索引i。
- 检查
- 遍历结束后,如果没有找到符合条件的索引对,返回
false。
举例分析,以 nums = [1,2,3,1], k = 3 为例:
- 初始化
map = {}。 - 遍历
nums:i = 0,nums[i] = 1,map更新为{1: 0}。i = 1,nums[i] = 2,map更新为{1: 0, 2: 1}。i = 2,nums[i] = 3,map更新为{1: 0, 2: 1, 3: 2}。i = 3,nums[i] = 1,发现1已存在,且abs(3 - 0) = 3,满足条件,返回true。
性能优化关键点:
- 哈希表的使用:通过使用哈希表来快速查找和更新元素索引,复杂度为 O(1)。
- 一次遍历:只需要遍历一次数组,时间复杂度为 O(n),其中 n 是数组的长度。
3. 代码实现
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>bool containsNearbyDuplicate(int* nums, int numsSize, int k) {int* map = (int*)calloc(200001, sizeof(int));for (int i = 0; i < numsSize; i++) {int num = nums[i] + 100000; // Offset to handle negative indicesif (map[num] != 0 && i - (map[num] - 1) <= k) {free(map);return true;}map[num] = i + 1; // Store index + 1 to distinguish from initial zero}free(map);return false;
}int main() {int nums[] = {1, 2, 3, 1};int k = 3;int numsSize = sizeof(nums) / sizeof(nums[0]);bool result = containsNearbyDuplicate(nums, numsSize, k);printf("Result: %s\n", result ? "true" : "false");return 0;
}
这段代码实现了一个函数 containsNearbyDuplicate,用于检查给定的整数数组 nums 中是否存在两个相同的元素,它们的下标之差的绝对值小于等于 k。
代码使用了哈希表的思想来优化查找效率。哈希表的大小为 HashSize,定义为 0x1fff + 1,即 8192。哈希表使用链表法解决哈希冲突,每个哈希桶都是一个链表的头节点。
函数 hash_reset 用于重置哈希表,释放所有节点的内存。
函数 containsNearbyDuplicate 的主要步骤如下:
- 重置哈希表。
- 遍历数组
nums,对于每个元素:- 计算哈希索引
nums[i] & 0x1fff,即将元素的低 13 位作为哈希索引。 - 在对应的哈希桶中查找是否存在相同的元素,且下标之差的绝对值小于等于
k,如果找到则返回true。 - 如果没有找到,则创建一个新的节点,存储当前元素的值和下标,插入到哈希桶的链表中。
- 计算哈希索引
- 如果遍历完整个数组都没有找到符合条件的元素对,则返回
false。
运行结果如下所示(仅供参考):

这段代码写得很暴力,优化空间很大:
- 哈希表的大小
HashSize可以根据实际情况进行调整,选择一个合适的大小以平衡内存使用和哈希冲突的概率。 - 可以考虑使用更高效的哈希函数,例如使用素数取模或者其他哈希算法,以减少哈希冲突的概率。
- 在插入新节点时,可以先判断链表的长度是否超过了一定的阈值,如果超过了,可以考虑将链表转换为其他数据结构,如红黑树,以提高查找效率。
- 可以考虑在插入新节点时,如果链表长度超过了
k,则可以直接删除链表头部的节点,因为它们的下标之差肯定大于k,不会影响结果。
4. 总结
本题主要考查对数组遍历和哈希表的应用能力。通过使用哈希表存储元素的最新索引,我们能够有效检查是否有符合条件的索引对。这种方法利用了哈希表快速查找和插入的特性,使得时间复杂度控制在 O(n) 内,适合处理大规模数据。
相关文章:
代码训练LeetCode(17)存在重复元素
代码训练(17)LeetCode之存在重复元素 Author: Once Day Date: 2024年5月7日 漫漫长路,才刚刚开始… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 219. 存在重复元素 II - 力扣(LeetCode)力扣 (LeetCode) 全球…...
运营模型—归因分析(Attribution Analysis)
运营模型—归因分析(Attribution Analysis) 随着互联网技术和业务的发展,广告投放相关的业务也随之兴起。那么广告投放的效果评估也就随之而来。广告的投放一般都是收费模式,所以选中的渠道商的好坏直接和自己的利益挂钩。于是,「归因分析」便最早应用在了广告投放行业。(…...
我必须要吹一波MATLAB 2024a,太牛逼了!|福利:附安装教程及下载地址
最近逛MATLAB官网,发现MATLAB 2024a版本已经Pre-release了,翻了下release note,不得不感叹,实在是太强了! 这次重点更新了四个工具箱: Computer Vision Toolbox Deep Learning Toolbox Instrument Contro…...
XMLHttpRequest与Axios详解
XMLHttpRequest发送请求 在JavaScript中,使用XMLHttpRequest()发送多个参数通常涉及到设置HTTP请求的Content-Type头部,并且将参数作为请求体的一部分发送。以下是一个示例,展示了如何发送包含多个参数的POST请求: var xhr new X…...
【区块链】智能合约简介
智能合约起源 智能合约这个术语至少可以追溯到1995年,是由多产的跨领域法律学者尼克萨博(NickSzabo)提出来的。他在发表在自己的网站的几篇文章中提到了智能合约的理念。他的定义如下:“一个智能合约是一套以数字形式定义的承诺&a…...
上海市计算机学会竞赛平台2024年1月月赛丙组成绩等第
题目描述 给定一个在 00 到 100100 之间的整数 𝑎a,请将它转成等第,规则如下: 9090 或以上为 A8080 或以上为 B7070 或以上为 C6060 或以上为 D5959 或以下为 F 输入格式 单个数字表示 𝑎a 输出格式 单个字符表示…...
【算法入门教育赛2】C.曼哈顿种类 C++题解与代码
比赛地址:https://www.starrycoding.com/contest/6 题目描述 牢 e e e知道在武汉有 n n n家自助店,第 i i i个自助店用坐标 ( x i , y i ) (x_i, y_i) (xi,yi)表示,因为武汉的街道都是互相垂直的,现在他想知道所有自助店之间…...
Electron使用 SQLite
在客户端开发中,无论是 PC 端,还是手机端,为了能够访问离线数据,数据经常需要保存到本地,IndexDB 可以用于存储本地数据,IndexDB 是一个对象存储,数据是以 key:value 的形式进行存储和访问的&am…...
怎样的跨网软件,可以实现网间数据的安全收发?
网络隔离已是较为常见的网络安全保护措施,比如防火墙、网闸、VLAN,云桌面虚拟环境等方面进行隔离。像一些科技研发型企业,不仅仅是内外网隔离,甚至还划分办公网、研发网、测试网、生产网等,防止研发资料、设计资料等敏…...
Sora惊艳亮相:AI技术掀起创作革命,影视产业迎来新风貌!
Sora平台近期发布了名为"Sora首次印象"的更新,为用户带来了令人瞩目的变化。该更新不仅展示了Sora平台的发展方向,还介绍了其在电影制作、广告宣传等领域的潜在应用。 同时,Sora的首席执行官Sam Altman与好莱坞影视工作室进行了会…...
Mac电脑安装打开APP显示问题已损坏 问题解决
当MAC电脑安装完软件打开时,显示文件已损坏,无法打开。搜了很多教程终于找到解决方案,记录下方便以后再用。 我的mac电脑是intel芯片的,如果你遇到这个问题,可以参考我的这个方案。 1.首先当打开软件后出现 “xx软件已…...
AI 数据观 | TapData Cloud + MongoDB Atlas:大模型与 RAG 技术有机结合,落地实时工单处理智能化解决方案
本篇为「AI 数据观」系列文章第二弹,在这里,我们将进一步探讨 AI 行业的数据价值。以 RAG 的智能工单应用场景为例,共同探索如何使用 Tapdata Cloud MongoDB Atlas 实现具备实时更新能力的向量数据库,为企业工单处理的智能化和自…...
Vulnhub靶机随笔-Hacksudo_Aliens
Vulnhub靶机Hacksudo_Aliens详解 攻击机Kali IP:192.168.3.44 靶机 IP:未知 系统:未知 A.信息收集 扫描靶机存活性 确定IP地址 1.命令:arp-scan -l 扫描靶机开放端口及其服务版本信息 2.命令 nmap -A -p- -sV 靶机IP地址 靶机开放三个端口,22ssh端口,80web端…...
抖店选品都怎么选品?什么样的产品更吸引人,更具有购买力?
大家好,我是电商花花。 抖店选品一直都是我们无货源商家的核心问题,不管是出单、还是爆单,店铺想要有销量的前提下都是选品。 很多人一上来就是就是选品,没有选品经验还瞎选品,结果到最后选了一堆出单的产品…...
将来会是Python、Java、Golang三足鼎立吗?
在开始前我有一些资料,是我根据网友给的问题精心整理了一份「 Java的资料从专业入门到高级教程」, 点个关注在评论区回复“888”之后私信回复“888”,全部无偿共享给大家!!! 软件工程里没有银弹ÿ…...
Java入门基础学习笔记16——运算符
package cn.ensource.operator;public class OperatorDemo1 {public static void main(String[] args) {// 目标:掌握基本的算术运算符的使用int a 10;int b 2;System.out.println(a b);System.out.println(a - b);System.out.println(a * b); // 20System.out.…...
golang中三种线程安全的MAP
一、map 是什么 map 是 Go 中用于存储 key-value 关系数据的数据结构,类似 C 中的 map,Python 中的 dict。Go 中 map 的使用很简单,但是对于初学者,经常会犯两个错误:没有初始化,并发读写。 1、未初始化的…...
C++笔试强训day16
目录 1.字符串替换 2.神奇数 3.DNA序列 1.字符串替换 链接 简单的遍历替换即可: class Solution { public:string formatString(string str, vector<char>& arg) {string ret;int k 0;for (int i 0; i < str.size(); i){if (str[i] %){ret arg…...
spsr 的恢复出错,导致 thumb 指令集的 it 条件运行指令运行异常,清晰的调试思路帮助快速解决问题
记一次调试过程 这是一个在 arm 架构上的 RTOS 上的调试过程。问题现象为使用 thumb 指令集的 libgcc 库的情况下,浮点运算随机出错。经过一番追踪调试,逐步缩小问题范围,最后定位问题,成功解决。 场景 在某款的国产 RTOS 上&a…...
mysql binlog 如何区分db
binlog不是InnoDB存储引擎特有的日志文件,是属于mysql server自己的日志文件。 提交事务的时候,同时会写入binlog 在MySQL中,Binary Log(binlog)记录了数据库更改操作的所有细节,对于实现数据复制、恢复以…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
MyBatis中关于缓存的理解
MyBatis缓存 MyBatis系统当中默认定义两级缓存:一级缓存、二级缓存 默认情况下,只有一级缓存开启(sqlSession级别的缓存)二级缓存需要手动开启配置,需要局域namespace级别的缓存 一级缓存(本地缓存&#…...
springboot 日志类切面,接口成功记录日志,失败不记录
springboot 日志类切面,接口成功记录日志,失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...
