leetcode题:287. 寻找重复数(中等)(存在环的单链表寻找环的入口点)

2024-03-15 15:48

本文主要是介绍leetcode题:287. 寻找重复数(中等)(存在环的单链表寻找环的入口点),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目描述:287. 寻找重复数(中等)

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2
示例 2:

输入: [3,1,3,4,2]
输出: 3
说明:

不能更改原数组(假设数组是只读的)。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字,但它可能不止重复出现一次。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、解题思路

使用快慢指针法,一个指针now走一步now= nums[now],一个指针pre走两步pre=nums[nums[pre]]。由于数组是连续并且有重复数字,相当于有环链表(不看答案想不出来)。然后问题就转换成求链表中环的入口(相同的数字就是环的入口,因为两个下标指向同一个数字,即当走两个相同的数字往下走一步的时候它们的位置相等的。

求环的入口(这里抄了一篇原理)

这里是出处:

https://blog.csdn.net/fynjy/article/details/47440049

 问题2:若存在环,如何找到环的入口点(即上图中的结点E)?
      解答:如图中所示,设链起点到环入口点间的距离为x,环入口点到问题1中fast与low重合点的距离为y,又设在fast与low重合时fast已绕环n周(n>0),且此时low移动总长度为s,则fast移动总长度为2s,环的长度为r。则
       s + nr = 2s,n>0      ①
       s = x + y               ②
      由①式得  s = nr                
      代入②式得
      nr = x + y
      x = nr - y                ③
      现让一指针p1从链表起点处开始遍历,指针p2从encounter处开始遍历,且p1和p2移动步长均为1。则当p1移动x步即到达环的入口点,由③式可知,此时p2也已移动x步即nr - y步。由于p2是从encounter处开始移动,故p2移动nr步是移回到了encounter处,再退y步则是到了环的入口点。也即,当p1移动x步第一次到达环的入口点时,p2也恰好到达了该入口点。

步骤

1、先定义快慢指针一个指针now走一步now= nums[now],一个指针pre走两步pre=nums[nums[pre]]。通过循环找到第一次相遇的位置。

2、定义一个新指针,从头开始next = 0;然后慢指针now和next同时一起每次走一步,直到相遇now == next。此时nums[now[就是重复的数字

三、代码

class Solution {
public:int findDuplicate(vector<int>& nums) {int pre = 0;int now = 0;now = nums[now];pre = nums[pre];pre = nums[pre];bool is_first = true;while(pre != now){//cout <<"pre="<<pre<<endl;//cout<<"now="<<now<<endl;pre = nums[pre];pre = nums[pre];now = nums[now];}//cout <<"pre="<<pre<<endl;//cout<<"now="<<now<<endl;int next = 0;while(nums[now] != nums[next]){now = nums[now];next = nums[next];//cout <<"next="<<next<<","<<nums[next]<<endl;//cout<<"now="<<now<<","<<nums[now]<<endl;}return nums[now];}
};

 

这篇关于leetcode题:287. 寻找重复数(中等)(存在环的单链表寻找环的入口点)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/812477

相关文章

Oracle数据库使用 listagg去重删除重复数据的方法汇总

《Oracle数据库使用listagg去重删除重复数据的方法汇总》文章介绍了在Oracle数据库中使用LISTAGG和XMLAGG函数进行字符串聚合并去重的方法,包括去重聚合、使用XML解析和CLO... 目录案例表第一种:使用wm_concat() + distinct去重聚合第二种:使用listagg,

MySQL中删除重复数据SQL的三种写法

《MySQL中删除重复数据SQL的三种写法》:本文主要介绍MySQL中删除重复数据SQL的三种写法,文中通过代码示例讲解的非常详细,对大家的学习或工作有一定的帮助,需要的朋友可以参考下... 目录方法一:使用 left join + 子查询删除重复数据(推荐)方法二:创建临时表(需分多步执行,逻辑清晰,但会

python 字典d[k]中key不存在的解决方案

《python字典d[k]中key不存在的解决方案》本文主要介绍了在Python中处理字典键不存在时获取默认值的两种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录defaultdict:处理找不到的键的一个选择特殊方法__missing__有时候为了方便起见,

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists