Floyd判圈算法——寻找重复数(C++)

287. 寻找重复数 - 力扣(LeetCode)

题目描述

        给定一个包含 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

题目思路

        这道题在LeetCode中是一道难度为中的题型,原因就是题目限制了不修改原数组并且只能用常量级的空间。

        假设没有限制,那一般的思路可以是以下几种:

        ①利用map容器,key就是nums中的数,value从0开始递增,如果value等于2时直接返回当前的nums[i],用一次循环即可,使用的空间为O(n);

        ②利用sort函数,对nums进行排序,由于数字都在[1, n]中并且只存在一个重复数字,用一次循环遍历,当nums[i - 1] == nums[i]时返回即可,但是修改了原数组;

        下面考虑题目限制,LeetCode官方提供了三种方法,其中一种方法利用的二进制,具体的可看官方题解,下面利用Floyd判圈算法解决这个题目。

对于Floyd算法原理可参照我的上一篇博客:Floyd判圈算法——环形链表(C++)-CSDN博客

为了方便理解,以数组:[1, 2, 3, 4, 5, 6, 4]为例:

怎么把这个数组抽象成龟兔赛跑问题呢?

抽象跑道

        从数组的第一个位置开始,nums[0]即为跑道的起点,由于nums[0] = 1, 那下一个点就是索引为1的点nums[1];由于nums[1] = 2, 那下一个点就是nums[2],以此类推……绘图如下: 

可以看到,我们所求的重复数就是环的入口点。 

过程推演

        最开始乌龟和兔子都在起始点1的位置,兔子的速度是乌龟的两倍,即乌龟向前走一步,兔子就向前走两步。

        第一步:寻找相遇点

        ①乌龟从1→2,兔子从1→3;

        ②乌龟从2→3,兔子从3→5;

        ③乌龟从3→4,兔子从5→4,在此刻乌龟与兔子相遇;

Notes:此时并没有结束,并不是所有的相遇点对应的值都是环的入口点,如果环上还有一个数字,相遇点就会发生改变。

        第二步:寻找环的入口点 

        将乌龟置为起点1处,将兔子置为相遇点4处,同步两者的速度为1:

        ①乌龟从1→2,兔子从4→5;

        ②乌龟从2→3,兔子从5→6;

        ③乌龟从3→4,兔子从6→4,在此刻乌龟与兔子相遇,这个时候对应的值才是正确的值,只是这个例子相遇点恰好在环的入口点上。

代码实现

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        //利用Floyd判圈算法
        int slow = 0;
        int fast = 0;
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);

        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

结果展示

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

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

相关文章

python基础语法笔记(有C语言基础之后)

input()用于输入&#xff0c;其有返回值&#xff08;即用户输入的值&#xff09;&#xff0c;默认返回字符串。括号里可放提示语句 一行代码若想分为多行来写&#xff0c;需要在每一行的末尾加上“\” 单个“/”表示数学中的除法&#xff0c;不会取整。“//”才会向下取整。 …

无人机之飞行规划与管理篇

无人机飞行规划与管理是确保无人机安全、高效且符合法规的运行的关键步骤。这一过程包括了对飞行任务的详细安排、航线的设定以及风险的评估和管理。下面简述这一过程的主要环节&#xff1a; 一、飞行目的和任务确定 在规划之初&#xff0c;必须明确无人机的飞行目的&#xf…

HTTPS理解

一个完整的HTTP连接 TCP三次握手接受窗口发送数据关闭连接 接受窗口是用来做什么呢&#xff1f; 它根据自身网络情况设置不同大小的值用来控制对方发送速度&#xff0c;避免对方发送太快&#xff0c;导致网络拥塞。 为什么TCP握手要三次&#xff1f; 1&#xff09;确认双方的…

单片机中有FLASH为啥还需要EEROM?

在开始前刚好我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「单片机的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01; 一是EEPROM操作简单&…

JDK11中zgc垃圾回收器的探索

背景 垃圾回收器主要做的事情 自动跟踪和管理程序中创建的对象&#xff0c;确定哪些对象仍在使用&#xff0c;哪些对象已经不再使用。回收那些不再使用的对象所占用的内存空间&#xff0c;使得这部分内存可以被重新使用。 1.1 传统垃圾回收器 垃圾回收器简述优缺点应用场景…

typora 两边太宽,设置宽度

步骤&#xff1a; 查看目前使用主题类型 文件 —> 偏好设置 —> 外观 —> 打开主题文件夹 修改对应的主题&#xff1a;max-width

在Linux下使用Docker部署chirpstack

目录 一、前言 二、chirpstack 1、chirpstack是什么 2、chirpstack组件 3、为什么选择Docker部署 三、Linux下部署过程 四、web界面部署过程 一、前言 本篇文章我是在Linux下使用 Docker 进行部署chirpstack&#xff0c;chirpstack采用的是v4 版本&#xff0c;v4 版本 与…

实时数仓搭建

项目概述 本项目针对实时数仓中的dim层&#xff0c;使用flik获取维度数据以及维度表结构把处理过的数据和维度表同步到habse中&#xff0c;同步采用的是雪花模型&#xff0c;遵循三范式&#xff0c;对维度数据进行实时的增删改查。 对维度表进行动态拆分功能。 动态拆分功能…

centos安装数据库同步工具sqoop并导入数据,导出数据,添加定时任务

目录 1.安装jdk 1.1上传jdk安装包到/opt目录下并解压 1.2解压 1.3配置环境变量 2.安装hadoop 2.1.下载hadoop 2.2.解压hadoop 2.3配置环境变量 3.安装sqoop 3.1下载 3.2解压 3.3下载依赖包并复制到指定位置 3.3.1下载commons-lang-2.6-bin.tar.gz 3.3.2将mysql-c…

【postgresql初级使用】用户与角色的关系,搭建数据库安全体系中的分权管理

用户角色管理 ​专栏内容&#xff1a; postgresql使用入门基础手写数据库toadb并发编程 个人主页&#xff1a;我的主页 管理社区&#xff1a;开源数据库 座右铭&#xff1a;天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物. 文章目录 用户角色管…

Nature Renderer 2022(植被渲染工具插件)

渲染大量详细的植被。 自然渲染器通过替换Unity的默认地形细节和树系统来提高植被渲染的质量。一切都适用于现有数据:使用相同的草地、植被和树木,并保留现有地形。我们只是升级您的渲染器。 Unity验证的解决方案 Nature Renderer受到25000多名开发人员的信任,是Unity验证的…

基于Make的c工程No compilation commands found报错

由于安装gcc时只安装了build-essential&#xff0c;没有将其添加到环境变量中&#xff0c;因此打开Make工程时&#xff0c;CLion会产生如下错误&#xff1a; 要解决这个问题&#xff0c;一个方法是将GCC添加到环境变量中&#xff0c;但是这个方法需要修改至少两个配置文件&…

请编写函数,删除字符串中指定位置下的字符,删除成功函数返回被删字符,否则返回空值

char arr_del(char* p, int pos) {if (pos> strlen(p) || pos<0){printf("这是一个无效下标\n");exit(1);}//到这里就是有效下标char ch p[pos];//把要删除的下标存储for (int i pos; p[i] ! \0; i){p[i] p[i 1];}return ch; } int main() {char arr[100];…

PFC电路中MOS管的选取3

MOS管的驱动波形 一个 MOS管在开通或者关断的时候&#xff0c;必定会经历一个线性区。这个线性区域在 Vgs波形上表现出一个平台&#xff0c;在这个平台的时候电流和电压的变化率是很大的&#xff0c;有很大的 dv/dt&#xff0c;di/dt &#xff0c;由于 di/dt变化非常大&#xf…

Transformer模型解析:走进自然语言处理的新时代

UPDATED&#xff1a;2023 年 1 月 27 日&#xff0c;本文登上 ATA 头条。&#xff08;注&#xff1a;ATA 全称 Alibaba Technology Associate&#xff0c;是阿里集团最大的技术社区&#xff09;UPDATED&#xff1a;2023 年 2 月 2 日&#xff0c;本文在 ATA 获得鲁肃点赞。&…

使用lv虚拟卷扩展磁盘

使用centos演示。 首先创建centos虚拟机。链接&#xff1a;VMWARE安装Centos8,并且使用ssh连接虚拟机-CSDN博客 1. 增加磁盘。 选中要扩容的虚拟机&#xff0c;右键选择设置&#xff0c;然后点击磁盘&#xff0c;选择添加。 这里选择NVM的磁盘。选择这种磁盘是为了保持与之前…

【Java】零散知识--感觉每条都有知识在进入脑子唤起回忆

1&#xff0c;什么是双亲委派 AppClassLoader在加载类时&#xff0c;会向上委派&#xff0c;取查找缓存。 AppClassLoader >>ExtClassLoader >>BootStrapClassLoader 情况一 向上委派时查找到了&#xff0c;直接返回。 情况二 当委派到顶层之后&#xff0c;缓…

python网络爬虫之Urllib

概述 urllib的request模块提供了最基本的构造HTTP请求的方法&#xff0c;使用它可以方便地实现请求的发送并得到响应&#xff0c;同时它还带有处理授权验证&#xff08;authentication&#xff09;、重定向&#xff08;redirection&#xff09;、浏览器Cookies以及其他内容。 …

java算法day11

二叉树的递归遍历二叉树的非递归遍历写法层序遍历 递归怎么写&#xff1f; 按照三要素可以保证写出正确的递归算法&#xff1a; 1.确定递归函数的参数和返回值&#xff1a; 确定哪些参数是递归的过程中需要处理的&#xff0c;那么就在递归函数里加上这个参数&#xff0c; 并且…

LabVIEW机器视觉技术在产品质量检测中有哪些应用实例

LabVIEW的机器视觉技术在产品质量检测中有广泛的应用&#xff0c;通过图像采集、处理和分析&#xff0c;实现对产品缺陷的自动检测、尺寸测量和定位校准&#xff0c;提高生产效率和产品质量。 1. 电子元器件质量检测 在电子制造业中&#xff0c;电子元器件的质量检测是确保产品…