LeetCode 热题 100_寻找重复数（100_287_中等_C++）（技巧）(暴力解法；哈希集合；二分查找)
LeetCode 热题 100_寻找重复数（100_287_中等_C++）
- 题目描述：
- 输入输出样例：
- 题解：
- 解题思路：
- 思路一（暴力解法）：
- 思路二（哈希集合）：
- 思路三（二分查找）：
- 代码实现
- 代码实现（思路一（暴力解法））：
- 代码实现（思路二（哈希集合））：
- 代码实现（思路三（二分查找））：
- 以思路二为例进行调试
题目描述：
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
输入输出样例：
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3：
输入：nums = [3,3,3,3,3]
输出：3
提示：
1 <= n <= 104
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
题解：
解题思路：
思路一（暴力解法）：
1、双重循环，进行枚举。
2、复杂度分析：
① 时间复杂度：O(n2)，n 代表数组中元素的个数，使用了双重循环。
② 空间复杂度：空间复杂度是 O(1)。
思路二（哈希集合）：
1、使用哈希集合来存储每个数字，若当前元素之前已经存在一个相同的值在哈希集合中，则当前元素为重复元素。
2、复杂度分析
① 时间复杂度：O(n)，n 代表数组中元素的个数，遍历一遍数组。
② 空间复杂度：O(n)，n 代表数组中元素的个数，使用哈希集合来存储元素。
思路三（二分查找）：
1、已知数字的范围为 [1 , n ] ,总共有 n + 1 个整数 且 nums 只有 一个重复的整数。则肯定存在 [1,2,…,n] 其中一个元素重复，则可采用二分查找。
- 假设有三个物品放两个抽屉那么必定有一个抽屉有两个物品
- 运用这个原理我们可以运用到此问题，若nums={1,3,4,2,2} 。n=4
- 假设我们统计 小于等于 2 元素的个数等于 3，3 个数放 1，2 两个位置必定有一个重复元素
- 那重复元素一定是 1 或者 2，那我们再查看 小于等于 1 元素的个数等于 1 则正好不重复，则重复元素必定是 2 。
2、复杂度分析
① 时间复杂度：O(nlogn)，其中 n 为 nums 数组的长度，采用了二分查找。
② 空间复杂度：O(1)。
代码实现
代码实现（思路一（暴力解法））：
class Solution1 {
public:// 定义函数 findDuplicate，接收一个整数数组 nums，返回数组中第一个重复的元素int findDuplicate(vector<int> &nums) {// 外层循环：遍历数组 nums 中的每个元素for (int l = 0; l < nums.size(); l++) {// 内层循环：从当前元素的下一个位置开始遍历// 目的是比较 nums[l] 与 nums[r] 是否相等for (int r = l + 1; r < nums.size(); r++) {// 如果找到重复的元素，返回该元素if (nums[l] == nums[r]) {return nums[l]; // 返回第一个重复的元素}}}// 如果没有找到重复元素，返回 0return -1;}
};
代码实现（思路二（哈希集合））：
class Solution2 {
public:// 定义函数 findDuplicate，接收一个整数数组 nums，返回数组中第一个重复的元素int findDuplicate(vector<int> &nums) {unordered_set<int> mp_set;for(auto &i:nums){if (mp_set.count(i)){return i;}mp_set.insert(i);}return -1;}
};
代码实现（思路三（二分查找））：
class Solution3 {
public:// findDuplicate 函数：用来查找给定数组中的重复数字int findDuplicate(vector<int> &nums) {int len = nums.size(); // 获取数组的长度int left = 1; // 左指针设为 1，因为数组元素范围从 1 到 nint right = nums.size() - 1; // 右指针设为 n-1，因为数组索引从 0 开始，元素值最大为 n// 使用二分查找的思想，判断重复数字的位置while (left < right) {// 计算中间值int mid = (left + right) / 2;// 统计数组中小于等于 mid 的元素个数int count = 0;for (auto &i : nums) {if (i <= mid) {count++; // 如果元素小于等于 mid，就增加计数}}// 如果小于等于 mid 的元素个数大于 mid，则说明重复的数字在左半部分if (count > mid) {right = mid; // 将右指针移到 mid，继续在左半部分查找} else {left = mid + 1; // 否则，重复的数字在右半部分，将左指针移到 mid + 1}}// 当 left == right 时，找到重复的数字return left;}
};
以思路二为例进行调试
#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;class Solution2 {
public:// 定义函数 findDuplicate，接收一个整数数组 nums，返回数组中第一个重复的元素int findDuplicate(vector<int> &nums) {unordered_set<int> mp_set;for(auto &i:nums){if (mp_set.count(i)){return i;}mp_set.insert(i);}return -1;}
};int main(int argc, char const *argv[])
{vector<int> nums={3,1,3,4,2};Solution2 s;cout<<s.findDuplicate(nums);return 0;
}LeetCode 热题 100_寻找重复数（100_287)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
相关文章：
)
LeetCode 热题 100_寻找重复数（100_287_中等_C++）（技巧）(暴力解法；哈希集合；二分查找)
LeetCode 热题 100_寻找重复数（100_287_中等_C） 题目描述：输入输出样例：题解：解题思路：思路一（暴力解法）：思路二（哈希集合）：思路三&am…...
多模态学习（三）—— ROPE位置编码：从理论到实践
ROPE位置编码：从理论到LLaMA的实践 一、前言 ROPE（Rotary Positional Embedding，旋转位置编码）是一种通过旋转矩阵将位置信息融入Token Embedding的编码方法。相比传统Transformer的绝对位置编码，ROPE能更灵活地建模…...
Redis——过期删除策略和内存
过期删除策略 Redis可以对key设置过期时间，因此需要有相应的机制将已过期的键值对删除 设置了过期时间的key会存放在过期字典中，可以用presist命令取消key过期时间 过期字典存储在redisDb结构中： typedef struct redisDb {dict *dict; …...
Selenium无法定位元素的几种解决方案详解
🍅 点击文末小卡片，免费获取软件测试全套资料，资料在手，涨薪更快 1、frame/iframe表单嵌套 WebDriver只能在一个页面上对元素识别与定位，对于frame/iframe表单内嵌的页面元素无法直接定位。 解决方法： …...
开源项目实战学习之YOLO11：12.3 ultralytics-models-sam-encoders.py源码分析
👉 点击关注不迷路 👉 点击关注不迷路 👉 另外，前些天发现了一个巨牛的AI人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。感兴趣的可以点击相关跳转链接。 点击跳转到网站。 ultralytics-models-sam 1.sam-modules-encoders.pyblocks.py： 定义模型中的各…...
Bitmap原理及Hive去重方式对比
1. 什么是 Bitmap？ Bitmap（位图）是一种用位（bit）来表示数据集合的数据结构。每个位代表一个元素是否存在，比如： 一个长度为N的bitmap，每一位对应一个元素的状态（0或1&a…...
力扣-比特位计数（统计一个数二进制下1的个数）
下面是题面 1.用c的内置函数__builtin_popcount（） 语法：__builtin_popcount（int x），函数会返回一个二进制下x所含的1的个数 2.直接数位枚举 这是最慢也是暴力做法，写法也很简单 用一个while循环…...
开源项目实战学习之YOLO11：12.2 ultralytics-models-sam-decoders.py源码分析
👉 点击关注不迷路 👉 点击关注不迷路 👉 另外，前些天发现了一个巨牛的AI人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。感兴趣的可以点击相关跳转链接。 点击跳转到网站。 ultralytics-models-sam 1.sam-modules-decoders.pyblocks.py： 定义模型中的各…...
Python训练营打卡Day28
浙大疏锦行 DAY 28 类的定义和方法 知识点回顾： 1.类的定义 2.pass占位语句 3.类的初始化方法 4.类的普通方法 5.类的继承：属性的继承、方法的继承 作业 题目1：定义圆（Circle）类 要求： 1.包含属性&#x…...
【前端基础】HTML元素隐藏的四个方法（display设置为none、visibikity设置为hidden、rgba设置颜色、opacity设置透明度）
HTML元素隐藏的四个方法 1、display设置为none 元素不显示出来。不占位置，也没有任何空间。就不存在一样。 2、visibility设置为hidden 默认：visible。元素可见设置为hidden：元素不可见，但是会占据这个元素应该占用的空间。 3、…...
STM32中的DMA
DMA介绍 什么是DMA? DMA（Direct Memory Access，直接存储器访问）提供在外设与内存、存储器和存储器之间的高速数据传输使用。它允许不同速度的硬件装置来沟通，而不需要依赖于CPU，在这个时间中，CPU对于内存…...
小型气象站应用之鱼塘养殖方案
概述 "看天吃饭"，在农村经常听到这句话，鱼塘也不例外。天气的急剧变化，或连续的不利天气都有可能造成鱼类"浮头"，甚至"翻肚子"，更甚至"翻塘"，一年白忙活了。 鱼塘…...
Makefile变量冲突与包含关系解析
Nuttx makefile每层独立，除非显示的通过include的方式包含。 Makefile调试技巧 打印变量 $(info CSRCS$(CSRCS))查看变量赋值过程 make --debugv在 Makefile 中，变量的作用域和可见性取决于 包含关系（include） 和 递归调用&…...
2025/517学习
对离群值怎么操作。这个就是拟合操作的。用更弯曲的曲线去拟合，如常见函数log 多元回归和单元回归 如题，如果我有多个自变量，来对一个因变量进行OLS回归，有没有operator可以做到？(ts_regression似乎只支持一个…...
浅谈前端架构设计与工程化
引言 在当今快速发展的Web开发领域，前端已经从简单的页面展示演变为复杂的应用程序开发。随着项目规模的扩大和团队协作的需求增加，良好的前端架构设计和工程化实践变得至关重要。本文将探讨如何构建可维护、可扩展的前端架构，并介绍现代前端…...
JMeter 教程：编写 POST 请求脚本访问百度
目录 ✅ 教程目的 🛠️ 环境要求 📄 实操步骤 第一步：启动 JMeter 第二步：添加测试计划和线程组 1.右键左侧 Test Plan（测试计划） 2.选择 Add → Threads (Users) → Thread Group（线程组…...
Typescript学习教程，从入门到精通，TypeScript 函数语法知识点及案例代码（5）
TypeScript 函数语法知识点及案例代码 TypeScript 提供了丰富的函数语法特性，使得函数定义更加灵活和强大。以下将详细介绍 TypeScript 中函数的相关语法，包括函数定义、可选参数、默认参数、剩余参数、重载函数、递归函数、匿名函数、箭头函数以及回调…...
【51单片机定时器/计数器】
目录 简介 定时器配置流程 1.配置定时器工作方式寄存器TMOD 2.配置中断寄存器TCON 3.定时时间计算公式 4.配置中断允许寄存器IE 5.使用中断函数完成中断 简介 定时器/计数器本质都是对脉冲信号进行计数，区别在于作为定时器时的脉冲信号来自于晶振12分频&…...
Oracle 的 ASSM 表空间
Oracle 的 ASSM（Automatic Segment Space Management）表空间 是一种自动管理段空间的技术，通过位图（Bitmap）机制跟踪数据块的使用情况，替代传统的手动管理（MSSM，即 Freelist 管理&am…...
C++学习：六个月从基础到就业——C++11/14：auto类型推导
C学习：六个月从基础到就业——C11/14：auto类型推导 本文是我C学习之旅系列的第四十一篇技术文章，也是第三阶段"现代C特性"的第三篇，主要介绍C11/14中的auto类型推导机制。查看完整系列目录了解更多内容。 引言 在现代C…...
select语句的书写顺序
一.MySQL SELECT语句的执行顺序 MySQL中SELECT语句的执行顺序与SQL语句的书写顺序不同，理解这个执行顺序对于编写高效查询非常重要。 1.标准SELECT语句的执行顺序 FROM子句（包括JOIN操作） 首先确定数据来源表执行表连接操作 WHERE子句 对F…...
OpenWebUI新突破，MCPO框架解锁MCP工具新玩法
大家好，Open WebUI 迎来重要更新，现已正式支持 MCP 工具服务器，但 MCP 工具服务器需由兼容 OpenAPI 的代理作为前端。mcpo 是一款实用代理，经测试，它能让开发者使用 MCP 服务器命令和标准 OpenAPI 服务器工具ÿ…...
【Day28】
总结： Python 通过缩进来定义代码块的结构。当解释器遇到像 def, class, if, for 这样的语句，并且后面跟着冒号 : 时，它就期望接下来会有一个或多个缩进的语句来构成这个代码块。如果它没有找到任何缩进的语句（即代码块是空的&am…...
STM32 | FreeRTOS 消息队列
01 一、概述 队列又称消息队列，是一种常用于任务间通信的数据结构，队列可以在任务与任务间、中断和任务间传递信息，实现了任务接收来自其他任务或中断的不固定长度的消息，任务能够从队列里面读取消息，当队列中的消…...
Vue-事件修饰符
事件修饰符 prevent （阻止默认事件） 超链接 点击事件 代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>事件修饰符</title><!-- 引入Vue --><script …...
c++函数调用运算符及类型转换运算符重载
author: hjjdebug date: 2025年 05月 17日 星期六 14:44:48 CST descrip: c函数调用运算符及类型转换运算符重载 文章目录 0. 前言. 运算符包括以下运算符.1. 运算符重载语句一般格式:2. 函数调用运算符：3. 类型转换运算符： 例如 int(); double(); bool(…...
如何在 Windows 10 或 11 中安装 PowerShellGet 模块？
PowerShell 是微软在其 Windows 操作系统上提供的强大脚本语言，可用于通过命令行界面自动化各种任务，适用于 Windows 桌面或服务器环境。而 PowerShellGet 是 PowerShell 中的一个模块，提供了用于从各种来源发现、安装、更新和发布模块的 cmdlet。 本文将介绍如何在 PowerS…...
84.评论日记
原链接 这个视频我发了四五条评论。评论内容甚至和下面这个视频内的其他评论一样。 找了另外的账号也发了。 发现，无论是我这个账号，还是其他的账号，评论都无法看到。 我大胆猜测有一种机制，某些官号会被设置成一种高检测的等…...
一周学会Pandas2 Python数据处理与分析-Pandas2数据添加修改删除操作
锋哥原创的Pandas2 Python数据处理与分析 视频教程： 2025版 Pandas2 Python数据处理与分析 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 对数据的修改、增加和删除在数据整理过程中时常发生。修改的情况一般是修改错误，还有一种情况是格式转换…...
荷兰国旗问题 之 指针划分区间问题
文章目录 首先介绍一下什么是荷兰国旗问题？问题描述为：给定一个由红色、白色和蓝色三种颜色组成的无序数组，将数组元素按颜色排序，使得所有红色元素在前，白色元素居中，蓝色元素在后。这里的 “颜色” 通常用…...
冒泡排序-java
public class BubbleSort{ public static void bubbleSort(int[] arr) { int n arr.length; boolean swapped; // 外层循环控制遍历的轮数 for (int i 0; i < n - 1; i) { swapped false; for (int j 0; …...
进阶-数据结构部分：2、常用排序算法
飞书文档https://x509p6c8to.feishu.cn/wiki/FfpIwIPtviMMb4kAn3Sc40ABnUh 常用排序算法 这几种算法都是常见的排序算法，它们的优劣和适用场景如下： 冒泡排序（Bubble Sort）：简单易懂，时间复杂度较高&…...
人工智能-自然语言与语音产品实现
一、语义相似度 （一）、文本向量化 1、文本向量化（Text Vectorization） 是自然语言处理（NLP）中的核心预处理步骤，旨在将人类语言的文本转换为计算机可处理的数值向量（数学表达&…...
阿里巴巴开源移动端多模态LLM工具——MNN
MNN 是一个高效且轻量级的深度学习框架。它支持深度学习模型的推理和训练，并在设备端的推理和训练方面具有行业领先的性能。目前，MNN 已集成到阿里巴巴集团的 30 多个应用中，如淘宝、天猫、优酷、钉钉、闲鱼等，覆盖了直播、短视频…...
SpringBootAdmin：全方位监控与管理SpringBoot应用
监控的意义 1. 监控服务状态是否宕机 2. 监控服务运行指标 (内存,虚拟机,线程,请求等) 3. 监控日志 4. 管理服务 (服务下线) 可视化监控平台 Spring Boot Admin, 开源社区项目, 用于管理和监控SpringBoot应用程序. 客户端注册到服务端, 通过HTTP请求方式, 服务端定期从客…...
SAP HCM 0008数据存储逻辑
0008信息类型：0008信息类型是存储员工基本薪酬的地方，因为很多企业都会都薪酬带宽，都会按岗定薪，所以在上线前为体现工资体系的标准化，都会在配置对应的薪酬关系，HCM叫间接评估，今天我们就分析下…...
】Config配置中心-ConfigServer端与Git通信（含源代码）（十三）)
【springcloud学习(dalston.sr1)】Config配置中心-ConfigServer端与Git通信（含源代码）（十三）
该系列项目整体介绍及源代码请参照前面写的一篇文章【springcloud学习(dalston.sr1)】项目整体介绍（含源代码）（一） springcloud学习（dalston.sr1）系统文章汇总如下： 【springcloud学习(dalston…...
2020CCPC河南省赛题解
A. 班委竞选 签到题，模拟。 #include <bits/stdc.h> #define x first #define y second #define int long long //#define double long doubleusing namespace std; typedef unsigned long long ULL ; typedef pair<int,int> PII ; typedef pair<d…...
C语言输入函数对比解析
目录 C语言输入函数全家福（和它们的秘密）fgetsgetsscanfgetcharfscanf函数对比表灵魂总结 哈哈，看来你正在和C语言的输入函数们玩“大家来找茬”！放心，我会用最接地气的方式给你讲明白，保证比看《甄嬛传》还…...
python四则运算计算器
python四则运算计算器 是谁说，python不好写计算器的，我亲自写个无ui的计算器功能，证明这是谣言 step1:C:\Users\wangrusheng\Downloads\num.txt 15 - 4 * 3 10 / 2(5 3) * 2 6 / 31/2 * 8 3/4 * 4 - 0.52.5 * (4 1.6) - 9 / 3-6 12 * (…...
BUUCTF——Nmap
BUUCTF——Nmap 进入靶场 类似于一个nmap的网站 尝试一下功能 没什么用 看看数据包 既然跟IP相关 伪造一个XXF看看 拼接了一下没什么用 果然没这么简单 尝试一下命令注入 构造payload 127.0.0.1 | ls 应该有过滤 加了个\ 直接构造个php木马上传试试 127.0.0.1 | <?…...
【Changer解码头详解及融入neck层数据的实验设计】
Changer解码头详解 ChangerEx中的 Changer 解码头（定义在 [changer.py](file://opencd\models\decode_heads\changer.py)）是基于双时相输入的，用于遥感变化检测任务。下面我将详细解释： 🎯 一、解码头输入数据来源 输…...
深度学习推理引擎---OpenVINO
OpenVINO（Open Visual Inference & Neural Network Optimization Toolkit）是英特尔开发的开源工具套件，旨在优化和加速深度学习模型在英特尔硬件（CPU、GPU、VPU、FPGA等）上的推理性能，同时支持从训练到…...
 方法)
JavaScript splice() 方法
1. JavaScript splice() 方法 1.1. 定义和用法 splice() 方法用于添加或删除数组中的元素。 注意：这种方法会改变原始数组。 返回值：如果删除一个元素，则返回一个元素的数组。 如果未删除任何元素，则返回空数组。 1.2. …...
数据库故障排查指南：解决常见问题，保障数据安全与稳定
数据库故障排查指南：解决常见问题，保障数据安全与稳定 📖 前言 数据库作为现代应用的核心组件，其稳定性直接影响业务连续性。本文总结六大常见数据库故障场景，提供快速排查思路与解决方案，助你化身"…...
gem5-gpu教程 第十章 关于topology 的Mesh network
问题一、L1和L2缓存之间的VI_hammer_fusion中指定了互连延迟，如何更改这些数字吗？ 我已经实现了一个网格拓扑来连接cpu内核和GPU SM，并对VI_hammer*和网格文件进行了所有必要的更改。我的问题是： 1. There is interconnect latency specified in VI_hammer_fusion betwee…...
【C/C++】C++返回值优化：RVO与NRVO全解析
文章目录 C返回值优化：RVO与NRVO全解析1 简介2 RVO vs NRVO3 触发条件4 底层机制5 应用场景6 验证与限制7 性能影响8 补充说明9 总结 C返回值优化：RVO与NRVO全解析 返回值优化（Return Value Optimization, RVO）是编译器通过消除临…...
使用 Kaniko来构建镜像
使用 Kaniko来构建镜像 Kaniko 是一种专注于容器镜像构建的开源工具，其核心设计理念与 Docker 存在显著差异。以下从功能定位、技术实现和适用场景三方面进行对比分析： 一、Kaniko 的核心特性 无需 Docker 守护进程 Kaniko 直接在容器或 Kubernetes 集…...
2025.05.17淘天机考笔试真题第三题
📌 点击直达笔试专栏 👉《大厂笔试突围》 💻 春秋招笔试突围在线OJ 👉 笔试突围OJ 03. 奇偶平衡树分割问题 问题描述 K小姐是一位园林设计师，她设计了一个由多个花坛组成的树形公园。每个花坛中种植了不同数量的花…...
history模式:让URL更美观
🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》、《前端求职突破计划》 🍚 蓝桥云课签约作者、…...