当前位置: 首页 > article >正文

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_寻找重复数&#xff08;100_287_中等_C&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;暴力解法&#xff09;&#xff1a;思路二&#xff08;哈希集合&#xff09;&#xff1a;思路三&am…...

NBA足球赛事直播源码体育直播M33模板赛事源码

源码名称&#xff1a;体育直播赛事扁平自适应M33直播模板源码 开发环境&#xff1a;帝国cms7.5 空间支持&#xff1a;phpmysql 带软件采集&#xff0c;可以挂着自动采集发布&#xff0c;无需人工操作&#xff01; 演示地址&#xff1a;NBA足球赛事直播源码体育直播M33模板赛事…...

【QT 项目部署指南】使用 Inno Setup 打包 QT 程序为安装包(超详细图文教程)

一、为什么需要打包成安装包&#xff1f; 在完成 QT 项目开发后&#xff0c;直接发布可执行文件&#xff08;.exe&#xff09;和依赖的 DLL 文件虽然可行&#xff0c;但存在以下问题&#xff1a; 用户体验差&#xff1a;用户需手动管理文件路径&#xff0c;容易因文件缺失导致…...

电子电器架构 --- 整车造车阶段四个重要节点

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 钝感力的“钝”,不是木讷、迟钝,而是直面困境的韧劲和耐力,是面对外界噪音的通透淡然。 生活中有两种人,一种人格外在意别人的眼光;另一种人无论…...

黑马点评-用户登录

文章目录 用户登录发送短信验证码注册/登录校验登录 用户登录 发送短信验证码 public Result sendCode(String phone, HttpSession session) {// 1.校验手机号if (RegexUtils.isPhoneInvalid(phone)) {// 2.如果不符合&#xff0c;返回错误信息return Result.fail("手机…...

ecmascript 第6版特性 ECMA-262 ES6

https://blog.csdn.net/zlpzlpzyd/article/details/146125018 在之前写的文章基础上&#xff0c;ES6在export和import的基础外&#xff0c;还有如下特性 特性说明let/const块级作用域变量声明>箭头函数Promise异步编程...

十二、Hive 函数

作者&#xff1a;IvanCodes 日期&#xff1a;2025年5月1日 专栏&#xff1a;Hive教程 在数据处理的广阔天地中&#xff0c;我们常常需要对数据进行转换、计算、清洗或提取特定信息。Hive 提供了强大的内置运算符和丰富的内置函数库&#xff0c;它们就像魔法师手中的魔法棒&…...

No More Adam: 新型优化器SGD_SaI

一.核心思想和创新点 2024年12月提出的SGD-SaI算法&#xff08;Stochastic Gradient Descent with Scaling at Initialization&#xff09;本质上是一种在训练初始阶段对不同参数块&#xff08;parameter block&#xff09;基于**梯度信噪比&#xff08;g-SNR, Gradient Signa…...

数据结构【AVL树】

AVL树 1.AVL树1.AVL的概念2.平衡因子 2.AVl树的实现2.1AVL树的结构2.2AVL树的插入2.3 旋转2.3.1 旋转的原则 1.AVL树 1.AVL的概念 AVL树可以是一个空树。 它的左右子树都是AVL树&#xff0c;且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树&#xff0c;通…...

C#将1GB大图裁剪为8张图片

C#处理超大图片&#xff08;1GB&#xff09;需要特别注意内存管理和性能优化。以下是几种高效裁剪方案&#xff1a; 方法1&#xff1a;使用System.Drawing分块处理&#xff08;内存优化版&#xff09; using System; using System.Drawing; using System.Drawing.Imaging; us…...

数据库——SQL约束窗口函数介绍

4.SQL约束介绍 &#xff08;1&#xff09;主键约束 A、基本内容 基本内容 p r i m a r y primary primary k e y key key约束唯一表示数据库中的每条记录主键必须包含唯一的值&#xff08;UNIQUE&#xff09;主键不能包含NULL值&#xff08;NOT NULL&#xff09;每个表都应…...

Linux系统启动相关:vmlinux、vmlinuz、zImage,和initrd 、 initramfs,以及SystemV 和 SystemD

目录 一、vmlinux、vmlinuz、zImage、bzImage、uImage 二、initrd 和 initramfs 1、initrd&#xff08;Initial RAM Disk&#xff09; 2、initramfs&#xff08;Initial RAM Filesystem&#xff09; 3、initrd vs. initramfs 对比 4. 如何查看和生成 initramfs 三、Syste…...

JSP链接MySQL8.0(Eclipse+Tomcat9.0+MySQL8.0)

所用环境 Eclipse Tomcat9.0 MySQL8.0.21(下载&#xff1a;MySQL Community Server 8.0.21 官方镜像源下载 | Renwole&#xff09; mysql-connector-java-8.0.21&#xff08;下载&#xff1a;MySQL :: Begin Your Download&#xff09; .NET Framework 4.5.2&#xff08;下…...

Python爬虫-爬取百度指数之人群兴趣分布数据,进行数据分析

前言 本文是该专栏的第56篇,后面会持续分享python爬虫干货知识,记得关注。 在本专栏之前的文章《Python爬虫-爬取百度指数之需求图谱近一年数据》中,笔者有详细介绍过爬取需求图谱的数据教程。 而本文,笔者将再以百度指数为例子,基于Python爬虫获取指定关键词的人群“兴…...

SEO长尾词与关键词优化实战

内容概要 在SEO优化体系中&#xff0c;长尾关键词与核心关键词的协同作用直接影响流量获取效率与用户转化路径。长尾词通常由3-5个词组构成&#xff0c;搜索量较低但意图明确&#xff0c;能精准触达细分需求用户&#xff1b;核心关键词则具备高搜索量与广泛覆盖能力&#xff0…...

机器学习-人与机器生数据的区分模型测试-数据处理1

附件为训练数据&#xff0c;总体的流程可以作为参考。 导入依赖 import pandas as pd import os import numpy as np from sklearn.model_selection import train_test_split,GridSearchCV from sklearn.ensemble import RandomForestClassifier,VotingClassifier from skle…...

HelloWorld

HelloWorld 新建一个java文件 文件后缀名为 .javahello.java【注意】系统可能没有显示文件后缀名&#xff0c;我们需要手动打开 编写代码 public class hello {public static void main(String[] args) {System.out.print(Hello,World)} }编译 javac java文件&#xff0c;会生…...

令牌桶和漏桶算法使用场景解析

文章目录 什么时候用令牌桶&#xff0c;什么时候用漏桶算法&#xff1f;&#xff1f;先放结论 两个算法一眼看懂什么时候选令牌桶&#xff1f;什么时候选漏桶&#xff1f;组合用法&#xff08;90% 的真实系统都会这么干&#xff09;小结记忆 对令牌桶和漏桶组合用法再次详细叙述…...

轻量、优雅、高扩展的事件驱动框架——Hibiscus-Signal

在现代企业级应用中&#xff0c;事件驱动架构&#xff08;EDA&#xff09;已成为解耦系统、提升扩展性的利器。今天给大家推荐一个非常优秀的国产轻量级事件驱动框架 —— Hibiscus Signal&#xff0c;它不仅天然整合 Spring Boot&#xff0c;还提供完整的事件生命周期支持&…...

SEO 优化实战:ZKmall模板商城的 B2C商城的 URL 重构与结构化数据

在搜索引擎算法日益复杂的今天&#xff0c;B2C商城想要在海量信息中脱颖而出&#xff0c;仅靠优质商品和营销活动远远不够。ZKmall模板商城以实战为导向&#xff0c;通过URL 重构与结构化数据优化两大核心策略&#xff0c;帮助 B2C 商城实现从底层架构到搜索展示的全面升级&…...

2020CCPC河南省赛题解

A. 班委竞选 签到题&#xff0c;模拟。 #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…...

数字万用表与指针万用表使用方法及注意事项

在电子测量领域&#xff0c;万用表是极为常用的工具&#xff0c;数字万用表和指针万用表各具特点。熟练掌握它们的使用方法与注意事项&#xff0c;能确保测量的准确性与安全性。下面为您详细介绍&#xff1a; 一 、数字万用表按钮功能 > 进入及退出手动量程模式 每 按 […...

虚拟主播肖像权保护,数字时代的法律博弈

首席数据官高鹏律师团队 在虚拟主播行业蓬勃发展的表象之下&#xff0c;潜藏着一场关乎法律边界的隐形战争。当一位虚拟偶像的3D模型被非法拆解、面部数据被批量复制&#xff0c;运营方惊讶地发现——传统的肖像权保护体系&#xff0c;竟难以完全覆盖这具由代码与数据构成的“…...

【读代码】端到端多模态语言模型Ultravox深度解析

一、项目基本介绍 Ultravox是由Fixie AI团队开发的开源多模态大语言模型,专注于实现音频-文本的端到端实时交互。项目基于Llama 3、Mistral等开源模型,通过创新的跨模态投影架构,绕过了传统语音识别(ASR)的中间步骤,可直接将音频特征映射到语言模型的高维空间。 核心优…...

RabbitMQ工作流程及使用方法

一、什么是RabbitMQ RabbitMQ 是一款基于 ‌AMQP&#xff08;高级&#xff0c;消息队列协议&#xff09;‌ 的开源消息中间件&#xff0c;专为分布式系统设计&#xff0c;用于实现应用程序间的异步通信&#xff0c;其核心功能是通过 ‌消息代理&#xff08;Message Broker&…...

Java 面向对象进阶:解锁多态、内部类与包管理

Java 面向对象进阶&#xff1a;解锁多态、内部类与包管理 &#x1f511; 在 Java 的面向对象编程中&#xff0c;多态赋予了对象“多种形态”的能力&#xff0c;内部类提供了更精细的代码组织方式&#xff0c;而包则帮助我们管理和组织大量的类。今天&#xff0c;我们将深入探讨…...

算法:分治法

实验内容 在一个2kⅹ2k个方格组成的棋盘中&#xff0c;若恰有一个方格与其他方格不同&#xff0c;则称该方格为特殊方格&#xff0c;且称该棋盘为一特殊棋盘。 显然&#xff0c;特殊方格出现的位置有4k 种情况&#xff0c;即k>0,有4k 种不同的特殊棋盘 棋盘覆盖&#xff1a…...

MySQL初阶:sql事务和索引

索引&#xff08;index&#xff09; 可以类似理解为一本书的目录&#xff0c;一个表可以有多个索引。 索引的意义和代价 在MySQL中使用select进行查询时会经过&#xff1a; 1.先遍历表 2.将条件带入每行记录中进行判断&#xff0c;看是否符合 3.不符合就跳过 但当表中的…...

docker部署第一个Go项目

1.前期准备 目录结构 main.go package mainimport ("fmt""github.com/gin-gonic/gin""net/http" )func main() {fmt.Println("\n .::::.\n .::::::::.\n :::::::::::\n …...

day27 python 装饰器

目录 一、装饰器的基本概念 示例&#xff1a;用装饰器优化质数查找函数 二、装饰器的高级用法 1. 支持任意参数的装饰器 2. 装饰器的返回值处理 在 Python 编程中&#xff0c;装饰器是一个非常强大的功能&#xff0c;它可以让其他函数或方法在不需要做任何代码修改的前提下…...